Submission #1258767

#TimeUsernameProblemLanguageResultExecution timeMemory
1258767uranium235Sjeckanje (COCI21_sjeckanje)Java
0 / 110
67 ms12368 KiB
//package ojuz; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); String[] first = reader.readLine().split(" "); int n = Integer.parseInt(first[0]), q = Integer.parseInt(first[1]); int[] a = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); int[] diff = new int[n - 1]; for (int i = 0; i < n - 1; i++) diff[i] = a[i + 1] - a[i]; SegTree tree = new SegTree(n - 1, diff); for (int i = 0; i < q; i++) { String[] query = reader.readLine().split(" "); int l = Integer.parseInt(query[0]) - 1, r = Integer.parseInt(query[1]) - 1, x = Integer.parseInt(query[2]); if (l > 0) tree.upd(l - 1, x, 0, n - 2, 1); if (r < n - 1) tree.upd(r, -x, 0, n - 2, 1); writer.write(String.valueOf(Math.max(Math.max(tree.a[1].grid[0][0], tree.a[1].grid[0][1]), Math.max(tree.a[1].grid[1][0], tree.a[1].grid[1][1])))); writer.newLine(); } writer.flush(); } static class SegTree { public final Node[] a; public final int n; public final int[] base; public SegTree(int n, int[] base) { this.n = n; this.a = new Node[4 * n]; this.base = base; build(0, n - 1, 1); } public void build(int l, int r, int v) { a[v] = new Node(); if (l == r) { a[v].set(base[l]); } else { int m = (l + r) / 2; build(l, m, 2 * v); build(m + 1, r, 2 * v + 1); a[v].merge(a[2 * v], a[2 * v + 1]); } } public void upd(int i, int x, int l, int r, int v) { if (l == r) { a[v].set(a[v].value + x); } else { int m = (l + r) / 2; if (i <= m) upd(i, x, l, m, 2 * v); else upd(i, x, m + 1, r, 2 * v + 1); a[v].merge(a[2 * v], a[2 * v + 1]); } } } static class Node { // closed, free, open public final long[][] grid = new long[3][3]; // signums for leftmost and rightmost numbers public int left, right, value = -1; public void set(int i) { for (long[] a : grid) Arrays.fill(a, Long.MIN_VALUE / 2); left = right = Integer.signum(i); if (i != 0) grid[0][2] = grid[2][0] = grid[0][0] = Math.abs(i); if (i != 0) grid[1][0] = grid[0][1] = 0; grid[1][1] = 0; value = i; } public void merge(Node l, Node r) { left = l.left; right = r.right; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { grid[i][j] = Math.max(Math.max(l.grid[i][0] + r.grid[1][j], l.grid[i][1] + r.grid[0][j]), l.grid[i][1] + r.grid[1][j]); if (l.right == r.left && l.right != 0) { grid[i][j] = Math.max(grid[i][j], l.grid[i][2] + r.grid[2][j]); } grid[i][j] = Math.max(grid[i][j], Long.MIN_VALUE / 2); } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...