제출 #1258772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258772		uranium235	Sjeckanje (COCI21_sjeckanje)	Java	110 / 110	1952 ms	245496 KiB

Main

//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);

//        System.out.println(tree.a[1].score());
//        System.out.println(Arrays.deepToString(tree.a[2].grid));
//        System.out.println(Arrays.deepToString(tree.a[3].grid));

        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(tree.a[1].score()));
            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] = grid[2][2] = 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);
            }
        }
        public long score() {
            return Math.max(Math.max(grid[0][0], grid[0][1]), Math.max(grid[1][0], grid[1][1]));
        }
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55