Tasks Details
hard
1.
NewMotorway
Given a number of cities located along a road, build a motorway between two cities to minimize the sum of distances from all cities to the easternmost one.
Task Score
100%
Correctness
100%
Performance
100%
There are N cities (numbered from 0 to N-1) located along a road. The K-th city is situated A[K] from the beginning of the road in the west. Cities are numbered in ascending order of position, and no two of them lie in the same place. Formally, A[K] < A[K + 1] holds for every K from 0 to N-2.
The time needed to travel east from city X to the easternmost city equals A[N - 1] - A[X] unless there is a city Y to the east of X (as cars can drive only to the east) with a motorway to the easternmost city built. Then, travel time decreases to A[Y] - A[X] (time spent on the motorway is not considered). If city X has a motorway built, then the travel time from it equals 0.
There are no motorways right now, but one from any city to the easternmost city is planned to be built. Decide where to build it in order to minimize the sum of travel times from every city to the easternmost one.
Write a function:
class Solution { public int solution(int[] A); }
that, given an array A of N integers, returns the minimum total travel time as described above.
As the result might be large, return its remainder when divided by 109 + 7.
Examples:
1. Given A = [1, 5, 9, 12], the function should return 7.
- With the motorway from the 0th city the travel times would be: 0 for the 0th city as it has a motorway, 7 for the 1st city and 3 for the 2nd city: that is 10 in total.
- With the motorway from the 1st city the travel times would be: 4 for the 0th city, 0 for the 1st city and 3 for the 2nd city: that is 7 in total.
- With the motorway from the 2nd city the travel times would be: 8 for the 0th city, 4 for the 1st city and 0 for the 2nd city: that is 12 in total.
2. If A = [5, 15], the function should return 0.
We can only build a motorway from the 0th city to the 1st. Travel time from the city to the motorway is 0, so 0 is the answer.
3. If A = [2, 6, 7, 8, 12], the function should return 9.
- With the motorway from the 0th city the total travel time is equal to 0 + 6 + 5 + 4 = 15.
- With the motorway from the 1st city the total travel time is equal to 4 + 0 + 5 + 4 = 13.
- With the motorway from the 2nd city the total travel time is equal to 5 + 1 + 0 + 4 = 10.
- With the motorway from the 3rd city the total travel time is equal to 6 + 2 + 1 + 0 = 9.
The answer is 9, because that is the minimum total time among all motorway placement possibilities.
4. If N = 20 and A[K] = K * (5 * 107) for each K from 0 to 19, the function should return 499999972. The minimal total time among all motorway placement possibilities is 4500000000, whose remainder when divided by 109 + 7 is 499999972.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [2..100,000];
- each element of array A is an integer within the range [0..1,000,000,000];
- the elements of A are all distinct;
- array A is sorted in ascending order.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 11
Time spent on task 67 minutes
Notes
not defined yet
Code: 21:10:13 UTC,
java,
autosave
Code: 21:17:16 UTC,
java11,
autosave
Code: 21:18:14 UTC,
java11,
autosave
Code: 21:18:39 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long mod = 10^9;
public int solution(int[] A) {
// write your code in Java SE 11
}
}
Code: 21:18:42 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long mod = 10^9 + 7;
public int solution(int[] A) {
// write your code in Java SE 11
}
}
Code: 21:18:53 UTC,
java11,
autosave
Code: 21:23:20 UTC,
java11,
autosave
Code: 21:23:47 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long mod = 10^9 + 7;
public static long[] fenwick = new long[];
public int solution(int[] A) {
}
}
Code: 21:24:10 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[];
public int solution(int[] A) {
}
}
Code: 21:24:13 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
public int solution(int[] A) {
}
}
Code: 21:24:27 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
p
public int solution(int[] A) {
}
}
Code: 21:24:48 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void constructFenwick(int[] A)
public int solution(int[] A) {
}
}
Code: 21:24:52 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void constructFenwick(int[] A) {
}
public int solution(int[] A) {
}
}
Code: 21:25:03 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void constructFenwick(int[] A) {
for(int i=0; i<)
}
public int solution(int[] A) {
}
}
Code: 21:25:15 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void constructFenwick(int[] A) {
for(int i=1; i<A.length; i++)
}
public int solution(int[] A) {
}
}
Code: 21:25:28 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
}
public int solution(int[] A) {
}
}
Code: 21:25:39 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick()
}
public int solution(int[] A) {
}
}
Code: 21:25:46 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i]);
}
public int solution(int[] A) {
}
}
Code: 21:26:03 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void updateFenwick(int i, int val) {
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i]);
}
public int solution(int[] A) {
}
}
Code: 21:26:12 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void updateFenwick(int i, int val) {
i = i
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i]);
}
public int solution(int[] A) {
}
}
Code: 21:26:15 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void updateFenwick(int i, int val) {
i = i + 1;
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i]);
}
public int solution(int[] A) {
}
}
Code: 21:26:27 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void updateFenwick(int i, int val) {
i = i + 1;
while(i < n)
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i]);
}
public int solution(int[] A) {
}
}
Code: 21:26:36 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void updateFenwick(int i, int val, int n) {
i = i + 1;
while(i < n)
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:26:45 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void updateFenwick(int i, int val, int n) {
i = i + 1;
while(i <= n) {
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:26:57 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void updateFenwick(int i, int val, int n) {
i = i + 1;
while(i <= n) {
fenwick
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:27:10 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void updateFenwick(int i, int val, int n) {
i = i + 1;
while(i <= n) {
fenwick[i] += val;
i = i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:27:19 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void updateFenwick(int i, int val, int n) {
i = i + 1;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:27:30 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void updateFenwick(int i, int val, int n) {
i = i + 1;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:27:42 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
}
void updateFenwick(int i, int val, int n) {
i = i + 1;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:28:21 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
}
void updateFenwick(int i, int val, int n) {
i = i + 1;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:28:25 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
}
void updateFenwick(int i, int val, int n) {
i = i + 1;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:28:40 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
int sum = 0;
}
void updateFenwick(int i, int val, int n) {
i = i + 1;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:28:56 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
int sum = 0;
i = i + 1;
while(i > 0) {
}
}
void updateFenwick(int i, int val, int n) {
i = i + 1;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:29:03 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:29:13 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:29:29 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
}
}
Code: 21:29:39 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
return 0;
}
}
Code: 21:29:44 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
constructFenwick(A)
return 0;
}
}
Code: 21:29:46 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:30:02 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:32:45 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:32:56 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick = new long[MAX];
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick()
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:33:13 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
public static long[] fenwick1 = new long[MAX];
public static long[] fenwick2 = new long[MAX];
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick()
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:33:27 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
public static final int MAX = 100_000;
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick()
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:33:30 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public static final long MOD = 10^9 + 7;
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick()
void constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:33:44 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick()
int[] constructFenwick(int[] A) {
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:33:58 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick()
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length]
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:34:09 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick()
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length];
for(int i=0; i<A.length; i++)
updateFenwick(i, A[i], A.length);
return fenwick;
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:34:20 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int i, int val, int n) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick()
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:34:29 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int[] fenwick, int i, int val) {
i++;
while(i <= n) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick()
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:34:40 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int[] fenwick, int i, int val) {
i++;
while(i <= fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick()
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:34:50 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int[] fenwick, int i, int val) {
i++;
while(i <= fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick()
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:35:23 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int[] fenwick, int i, int val) {
i++;
while(i <= fenwick.length - 1) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick()
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:35:33 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int[] fenwick, int i, int val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick()
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:35:43 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int[] fenwick, int i, int val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick() {
}
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:35:54 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int[] fenwick, int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int[] fenwick, int i, int val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
void updateRangeFenwick() {
}
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:36:21 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int[] fenwick, int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int[] fenwick, int i, int val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void updateRangeFenwick() {
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:36:39 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int[] fenwick, int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int[] fenwick, int i, int val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void sumFenwick() {
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:36:57 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int[] fenwick, int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int[] fenwick, int i, int val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void sumFenwick2(int i, int f1[], int f2[]) {
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:37:04 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
void getSum(int[] fenwick, int i) {
int sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
}
void updateFenwick(int[] fenwick, int i, int val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void sumFenwick2(int i, int f1[], int f2[]) {
return
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:37:13 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(int[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(int[] fenwick, int i, int val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void sumFenwick2(int i, int f1[], int f2[]) {
return
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:37:17 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(int[] fenwick, int i, int val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void sumFenwick2(int i, int f1[], int f2[]) {
return
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:37:22 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, int val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void sumFenwick2(int i, int f1[], int f2[]) {
return
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:37:25 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
int[] constructFenwick(int[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void sumFenwick2(int i, int f1[], int f2[]) {
return
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:37:35 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(long[] A) {
int[] fenwick = new int[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void sumFenwick2(int i, int f1[], int f2[]) {
return
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:37:42 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(long[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void sumFenwick2(int i, int f1[], int f2[]) {
return
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:37:48 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void sumFenwick2(int i, int f1[], int f2[]) {
return
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:38:10 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void sumFenwick2(int i, int f1[], int f2[]) {
return ()
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:38:27 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void sumFenwick2(int i, int f1[], int f2[]) {
return getSum(f1, i);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:38:36 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
void sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:38:49 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:38:59 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum();
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:39:14 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:40:12 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:40:23 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick()
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:40:34 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[],)
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:40:57 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:41:07 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick()
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:41:19 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:41:32 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:41:45 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val);
updateFenwick(f2, l, val);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:42:06 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:42:36 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:43:06 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return sum(r, f1, f2) - sum(l - 1, f1, f2);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:43:20 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
constructFenwick(A);
return 0;
}
}
Code: 21:43:51 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
constructFenwick(A);
for(int i = 0; i < n; i++) {
}
return 0;
}
}
Code: 21:44:09 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
constructFenwick(A);
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:44:19 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
constructFenwick(A);
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:45:02 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
longconstructFenwick(A);
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:45:25 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
long[] f1 = constructFenwick(A);
long[] f2 = new long[f1.length];
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:45:51 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
long[] f1 = constructFenwick(A);
long[] f2 = new long[f1.length];
long minimal
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:46:06 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
long[] f1 = constructFenwick(A);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:46:28 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
long[] f1 = constructFenwick(A);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:47:10 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
long[] f1 = constructFenwick(A);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:47:25 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
long[] f1 = constructFenwick(A);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:48:01 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
long[] f1 = constructFenwick(A);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:48:15 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = constructFenwick(A);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:48:56 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = constructFenwick(A);
long[] f2 = new long[f1.length];
long minimal = ;
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:49:26 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = constructFenwick(A);
long[] f2 = new long[f1.length];
long minimal = ;
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:49:56 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens
long[] f1 = constructFenwick(A);
long[] f2 = new long[f1.length];
long minimal = ;
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:50:13 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(A);
long[] f2 = new long[f1.length];
long minimal = ;
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:50:24 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = ;
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:50:34 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
}
return 0;
}
}
Code: 21:50:46 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick();
}
return 0;
}
}
Code: 21:51:03 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, val, 0, i);
}
return 0;
}
}
Code: 21:51:33 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, lens, 0, i);
}
return 0;
}
}
Code: 21:51:45 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return 0;
}
}
Code: 21:52:36 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, lens[i], 0, i);
l
}
return 0;
}
}
Code: 21:53:00 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2);
}
return 0;
}
}
Code: 21:53:10 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2);
}
return 0;
}
}
Code: 21:53:25 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2);
}
return 0;
}
}
Code: 21:53:36 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(int l, int r, long[] f1, long[] f2) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return 0;
}
}
Code: 21:53:56 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return 0;
}
}
Code: 21:54:06 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, );
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return 0;
}
}
Code: 21:54:22 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, );
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return 0;
}
}
Code: 21:55:03 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return 0;
}
}
Code: 21:55:28 UTC,
java11,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return 0;
}
}
Analysis
expand all
Example tests
1.
0.004 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5 at Solution.getSum(Solution.java:14) at Solution.sumFenwick2(Solution.java:41) at Solution.sumRangeFenwick(Solution.java:53) at Solution.solution(Solution.java:71) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
1.
0.004 s
OK
1.
0.004 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 6 out of bounds for length 6 at Solution.getSum(Solution.java:14) at Solution.sumFenwick2(Solution.java:41) at Solution.sumRangeFenwick(Solution.java:53) at Solution.solution(Solution.java:71) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
1.
0.004 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 21 out of bounds for length 21 at Solution.getSum(Solution.java:14) at Solution.sumFenwick2(Solution.java:41) at Solution.sumRangeFenwick(Solution.java:53) at Solution.solution(Solution.java:71) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
Code: 21:55:34 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return minimal;
}
}
Code: 21:55:40 UTC,
java11,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return minimal;
}
}
Analysis
Compile error
Solution.java:77: error: incompatible types: possible lossy conversion from long to int
return minimal;
^
1 error
Code: 21:55:50 UTC,
java11,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Analysis
expand all
Example tests
1.
0.004 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5 at Solution.getSum(Solution.java:14) at Solution.sumFenwick2(Solution.java:41) at Solution.sumRangeFenwick(Solution.java:53) at Solution.solution(Solution.java:71) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
1.
0.004 s
OK
1.
0.004 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 6 out of bounds for length 6 at Solution.getSum(Solution.java:14) at Solution.sumFenwick2(Solution.java:41) at Solution.sumRangeFenwick(Solution.java:53) at Solution.solution(Solution.java:71) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
1.
0.004 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 21 out of bounds for length 21 at Solution.getSum(Solution.java:14) at Solution.sumFenwick2(Solution.java:41) at Solution.sumRangeFenwick(Solution.java:53) at Solution.solution(Solution.java:71) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
Code: 21:56:13 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 21:56:15 UTC,
java11,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = 10^9 + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Analysis
expand all
Example tests
1.
0.004 s
WRONG ANSWER,
got 0 expected 7
1.
0.004 s
OK
1.
0.004 s
WRONG ANSWER,
got 6 expected 9
1.
0.004 s
WRONG ANSWER,
got 2 expected 499999972
Code: 21:57:44 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = Math. + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 21:57:55 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)Math.exp(10, 9) + 7;
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 21:58:05 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.exp(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 21:58:11 UTC,
java11,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.exp(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Analysis
Compile error
Solution.java:8: error: method exp in class Math cannot be applied to given types;
static final long MOD = (long)(Math.exp(10, 9) + 7);
^
required: double
found: int,int
reason: actual and formal argument lists differ in length
1 error
Code: 21:58:27 UTC,
java11,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Analysis
expand all
Example tests
1.
0.004 s
WRONG ANSWER,
got 49 expected 7
1.
0.004 s
OK
1.
0.004 s
WRONG ANSWER,
got 84 expected 9
1.
0.004 s
WRONG ANSWER,
got 44966029 expected 499999972
Code: 22:01:54 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:02:04 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
long[] constructFenwick2(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:02:18 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = constructFenwick(lens);
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:02:38 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = new long[A.length + 1]
long[] f2 = new long[f1.length];
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:02:53 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < )
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:03:06 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick();
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:03:36 UTC,
java11,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:03:41 UTC,
java11,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
int[] lens = new int[A.length];
for(int i = 0; i < A.length; i++)
lens[i] = A[A.length - 1] - A[i];
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Analysis
expand all
Example tests
1.
0.004 s
WRONG ANSWER,
got 13 expected 7
1.
0.004 s
OK
1.
0.004 s
WRONG ANSWER,
got 19 expected 9
1.
0.004 s
WRONG ANSWER,
got 89934466 expected 499999972
Code: 22:05:53 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -lens[i], 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:06:15 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:06:45 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A, i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:06:58 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:07:29 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i,);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:07:40 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, lens[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:07:51 UTC,
java11,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)minimal;
}
}
Analysis
expand all
Example tests
1.
0.004 s
OK
1.
0.004 s
OK
1.
0.008 s
OK
1.
0.008 s
WRONG ANSWER,
got 205032669 expected 499999972
Code: 22:08:14 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:08:24 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2)) % MOD;
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:09:12 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return (sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:09:23 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)minimal;
}
}
Code: 22:09:33 UTC,
java11,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], int val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)(minimal % MOD);
}
}
Analysis
expand all
Example tests
1.
0.004 s
OK
1.
0.004 s
OK
1.
0.004 s
OK
1.
0.004 s
WRONG ANSWER,
got 205032669 expected 499999972
Code: 22:10:37 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], long val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)(minimal % MOD);
}
}
Code: 22:10:50 UTC,
java11,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], long val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)(minimal % MOD);
}
}
Analysis
expand all
Example tests
1.
0.004 s
OK
1.
0.008 s
OK
1.
0.004 s
OK
1.
0.004 s
WRONG ANSWER,
got 299999958 expected 499999972
Code: 22:13:23 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
s
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], long val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)(minimal % MOD);
}
}
Code: 22:13:35 UTC,
java11,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
sum %= MOD;
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return (getSum(f1, i) * i - getSum(f2, i)) % MOD;
}
void updateRangeFenwick(long f1[], long f2[], long val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)(minimal % MOD);
}
}
Code: 22:13:57 UTC,
java11,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], long val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)(minimal % MOD);
}
}
Code: 22:14:04 UTC,
java11,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], long val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)(minimal % MOD);
}
}
Analysis
Code: 22:16:35 UTC,
java11,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], long val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)(minimal % MOD);
}
}
Analysis
Code: 22:16:42 UTC,
java11,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
static final long MOD = (long)(Math.pow(10, 9) + 7);
long getSum(long[] fenwick, int i) {
long sum = 0;
i++;
while(i > 0) {
sum += fenwick[i];
i -= i & (-i);
}
return sum;
}
void updateFenwick(long[] fenwick, int i, long val) {
i++;
while(i < fenwick.length) {
fenwick[i] += val;
i += i & (-i);
}
}
long[] constructFenwick(int[] A) {
long[] fenwick = new long[A.length + 1];
for(int i=0; i<A.length; i++)
updateFenwick(fenwick, i, A[i]);
return fenwick;
}
/* ------------------ */
long sumFenwick2(int i, long f1[], long f2[]) {
return getSum(f1, i) * i - getSum(f2, i);
}
void updateRangeFenwick(long f1[], long f2[], long val, int l, int r) {
updateFenwick(f1, l, val);
updateFenwick(f1, r + 1, -val);
updateFenwick(f2, l, val * (l - 1));
updateFenwick(f2, r + 1, -val * r);
}
long sumRangeFenwick(long[] f1, long[] f2, int l, int r) {
return sumFenwick2(r, f1, f2) - sumFenwick2(l - 1, f1, f2);
}
public int solution(int[] A) {
if(A.length == 2)
return 0;
long[] f1 = new long[A.length + 1];
long[] f2 = new long[A.length + 1];
for(int i = 0; i < A.length; i++)
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], i, i);
long minimal = Long.MAX_VALUE;
for(int i = 0; i < A.length; i++) {
updateRangeFenwick(f1, f2, -(A[A.length - 1] - A[i]), 0, i);
long newLen = sumRangeFenwick(f1, f2, 0, A.length - 1);
minimal = Math.min(minimal, newLen);
updateRangeFenwick(f1, f2, A[A.length - 1] - A[i], 0, i);
}
return (int)(minimal % MOD);
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
equal_adjacent_distances
Test cases where distances between adjacent cities are equal. N <= 100.
Test cases where distances between adjacent cities are equal. N <= 100.
✔
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
6.
0.004 s
OK
7.
0.004 s
OK
8.
0.004 s
OK
9.
0.004 s
OK
adjacent_distances_non_decreasing
Test cases where distances between adjacent cities are non-decreasing. N <= 100.
Test cases where distances between adjacent cities are non-decreasing. N <= 100.
✔
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
adjacent_distances_non_increasing
Test cases where distances between adjacent cities are non-increasing. N <= 100.
Test cases where distances between adjacent cities are non-increasing. N <= 100.
✔
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
modulo_needed
Test cases where the result is big and its division remainder has to be returned. N <= 100. Score x 0.5.
Test cases where the result is big and its division remainder has to be returned. N <= 100. Score x 0.5.
✔
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
int64_needed
Test cases where the result is big and 64-bit variables are needed. N <= 100. Score x 0.5.
Test cases where the result is big and 64-bit variables are needed. N <= 100. Score x 0.5.
✔
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
expand all
Performance tests
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
equal_adjacent_distances_big
Test cases where distances between adjacent cities are equal. N <= 40,000. Score x 2.
Test cases where distances between adjacent cities are equal. N <= 40,000. Score x 2.
✔
OK
1.
0.284 s
OK
2.
0.184 s
OK
3.
0.152 s
OK
adjacent_distances_non_increasing_big
Test cases where distances between adjacent cities are non-increasing. N <= 40,000. Score x 2.
Test cases where distances between adjacent cities are non-increasing. N <= 40,000. Score x 2.
✔
OK
1.
0.240 s
OK
2.
0.328 s
OK
3.
0.228 s
OK
1.
0.496 s
OK
2.
0.540 s
OK
3.
0.304 s
OK
4.
0.756 s
OK
5.
0.104 s
OK
6.
0.728 s
OK
7.
0.004 s
OK
8.
0.888 s
OK