package Tasks;
import Code.IO.InputReader;
import java.io.PrintWriter;
import java.util.*;
public class jumps {
public void solve(int testNumber, InputReader in, PrintWriter out) {
int N = in.nextInt();
int[][] A = new int[N][2];
int[] F = new int[N];
for (int i = 0; i < N; i++) {
A[i][0] = in.nextInt();
F[i] = A[i][0];
A[i][1] = i;
}
Arrays.sort(A, new Comparator<int[]>() {
@Override
public int compare(int[] ints, int[] t1) {
return Integer.compare(ints[0], t1[0]);
}
});
TreeSet<Integer> set = new TreeSet<>();
ArrayList<Integer>[] pair = new ArrayList[N];
for (int i = 0; i < N; i++) {
pair[i] = new ArrayList<>();
}
for (int i = N-1; i >= 0; i--) {
if (set.lower(A[i][1]) != null) {
pair[set.lower(A[i][1])].add(A[i][1]);
}
if (set.higher(A[i][1]) != null) {
pair[A[i][1]].add(set.higher(A[i][1]));
}
set.add(A[i][1]);
}
int Q = in.nextInt();
ArrayList<int[]>[] query = new ArrayList[N];
for (int i = 0; i < Q; i++) {
int l = in.nextInt()-1;
int r = in.nextInt()-1;
if (query[l] == null) {
query[l] = new ArrayList<>();
}
query[l].add(new int[]{r, i});
}
int[] ans = new int[Q];
SegmentTree seg = new SegmentTree(F);
for (int l = N-2; l >= 0; l--) {
if (pair[l] != null) {
for (int a : pair[l]) {
seg.upd(1, 0, N - 1, 2 * a - l, N - 1, F[a] + F[l]);
}
}
if (query[l] != null) {
for (int[] r : query[l]) {
ans[r[1]] = seg.query(1, 0, N - 1, l + 2, r[0]);
}
}
}
for (int i : ans) {
out.println(i);
}
}
class SegmentTree {
int[] max;
int[] lzy;
int[] oriMax;
int[] arr;
SegmentTree(int[] arr) {
this.arr = arr;
max = new int[4*arr.length];
oriMax = new int[4*arr.length];
lzy = new int[4*arr.length];
setOri(1, 0, arr.length-1);
}
void setOri(int n, int tl, int tr) {
if (tl == tr) {
oriMax[n] = arr[tl];
}
else {
int tm = (tl + tr) / 2;
setOri(2*n, tl, tm);
setOri(2*n+1, tm+1, tr);
oriMax[n] = Math.max(oriMax[2*n], oriMax[2*n+1]);
}
}
void push(int n) {
lzy[2*n] = Math.max(lzy[2*n], lzy[n]);
lzy[2*n+1] = Math.max(lzy[2*n+1], lzy[n]);
max[2*n] = Math.max(max[2*n], oriMax[2*n] + lzy[2*n]);
max[2*n+1] = Math.max(max[2*n+1], oriMax[2*n+1] + lzy[2*n+1]);
lzy[n] = 0;
}
void upd(int n, int tl, int tr, int l, int r, int val) {
if (l <= tl && tr <= r) {
max[n] = Math.max(max[n], oriMax[n] + val);
lzy[n] = Math.max(lzy[n], val);
}
else if (l > tr || r < tl) {
return;
}
else {
push(n);
int tm = (tl + tr)/2;
upd(2*n, tl, tm, l, r, val);
upd(2*n+1, tm+1, tr, l, r, val);
max[n] = Math.max(max[2*n], max[2*n+1]);
}
}
int query(int n, int tl, int tr, int l, int r) {
if (l <= tl && tr <= r) {
return max[n];
}
else if (l > tr || r < tl) {
return 0;
}
else {
push(n);
int tm = (tl + tr)/2;
return Math.max(query(2*n, tl, tm, l, r),
query(2*n+1, tm+1, tr, l, r));
}
}
}
}
Compilation message
jumps.java:3: error: package Code.IO does not exist
import Code.IO.InputReader;
^
jumps.java:8: error: cannot find symbol
public void solve(int testNumber, InputReader in, PrintWriter out) {
^
symbol: class InputReader
location: class jumps
Note: jumps.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
2 errors
