oj.uz

Submission #255294

# Submission time Handle Problem Language Result Execution time Memory
255294 2020-07-31T17:09:11 Z model_code Progression (NOI20_progression) Java 11
83 / 100
 5000 ms 208864 KB 
import java.io.*;
import java.util.*;
import java.lang.Math.*;

public class Progression {
    static long[] D;
    static long[] B;

    static class qval {
        public int len, prefix_len, suffix_len, subarray_len;
        public long sum, prefix_val, suffix_val, subarray_val;
        public qval() {}
        public void init(long val) {
            len = 1; sum = val;
            subarray_len = 0;
            subarray_val = 0;
            prefix_len = suffix_len = 1;
            prefix_val = suffix_val = val;
        }
        public void add(long val) {
            prefix_val += val;
            suffix_val += val;
            subarray_val += val;
            sum += val * len;
        }
        public void set(long val) {
            prefix_val = suffix_val = subarray_val = val;
            prefix_len = suffix_len = len;
            subarray_len = Math.max(0, len - 2);
            sum = val * len;
        }
    }

    static class SegmentTree {
        private qval[] V;
        private boolean[] lset;
        private long[] lazy_set;
        private long[] lazy_add;
        SegmentTree() {
            lazy_set = new long[1500010];
            lazy_add = new long[1500010];
            lset = new boolean[1500010];
            V = new qval[1500010];
        }
        public void build(int node, int S, int E) {
            V[node] = new qval();
            if (S == E) {
                V[node].init(B[S]);
                return;
            }
            int M = S + (E - S) / 2;
            build(node << 1, S, M);
            build(node << 1 | 1, M + 1, E);
            combine(V[node], V[node << 1], V[node << 1 | 1]);
        }
        private void combine(qval ret, qval left, qval right) {
            ret.len = left.len + right.len;
            ret.sum = left.sum + right.sum;

            ret.prefix_len = left.prefix_len;
            ret.prefix_val = left.prefix_val;
            if (left.prefix_len == left.len && left.prefix_val == right.prefix_val) {
                ret.prefix_len = left.len + right.prefix_len;
                ret.prefix_val = left.prefix_val;
            }

            ret.suffix_len = right.suffix_len;
            ret.suffix_val = right.suffix_val;
            if (right.suffix_len == right.len && left.suffix_val == right.suffix_val) {
                ret.suffix_len = right.len + left.suffix_len;
                ret.suffix_val = right.suffix_val;
            }

            if (left.subarray_len > right.subarray_len) {
                ret.subarray_len = left.subarray_len;
                ret.subarray_val = left.subarray_val;
            } else {
                ret.subarray_len = right.subarray_len;
                ret.subarray_val = right.subarray_val;
            }
            if (Math.min(left.len - 1, left.suffix_len) > ret.subarray_len) {
                ret.subarray_len = Math.min(left.len - 1, left.suffix_len);
                ret.subarray_val = left.suffix_val;
            }
            if (Math.min(right.len - 1, right.prefix_len) > ret.subarray_len) {
                ret.subarray_len = Math.min(right.len - 1, right.prefix_len);
                ret.subarray_val = right.prefix_val;
            }
            if (left.suffix_val == right.prefix_val &&
                Math.min(left.len - 1, left.suffix_len) +
                Math.min(right.len - 1, right.prefix_len) > ret.subarray_len) {
                ret.subarray_len = Math.min(left.len - 1, left.suffix_len) +
                    Math.min(right.len - 1, right.prefix_len);
                ret.subarray_val = left.suffix_val;
            }
        }
        private void push(int node) {
            if (lset[node]) {
                rset(node << 1, lazy_set[node]);
                rset(node << 1 | 1, lazy_set[node]);
                lset[node] = false;
                lazy_set[node] = 0;
            }
            if (lazy_add[node] != 0) {
                radd(node << 1, lazy_add[node]);
                radd(node << 1 | 1, lazy_add[node]);
                lazy_add[node] = 0;
            }
        }
        public void radd(int node, long QV) {
            if (lset[node]) V[node].set(lazy_set[node] += QV);
            else {
                lazy_add[node] += QV;
                V[node].add(QV);
            }
        }
        public void rset(int node, long QV) {
            lset[node] = true;
            lazy_add[node] = 0;
            V[node].set(lazy_set[node] = QV);
        }
        public qval query(int node, int S, int E, int QS, int QE) {
            if (QS <= S && E <= QE) return V[node];
            push(node);
            int M = S + (E - S) / 2;
            if (QE <= M) return query(node << 1, S, M, QS, QE);
            if (QS > M) return query(node << 1 | 1, M + 1, E, QS, QE);
            qval ret = new qval();
            combine(ret, query(node << 1, S, M, QS, M), query(node << 1 | 1, M + 1, E, M + 1, QE));
            return ret;
        }
        public void add(int node, int S, int E, int QS, int QE, long QV) {
            if (QS <= S && E <= QE) {
                radd(node, QV);
                return;
            }
            push(node);
            int M = S + (E - S) / 2;
            if (QE <= M) add(node << 1, S, M, QS, QE, QV);
            else if (QS > M) add(node << 1 | 1, M + 1, E, QS, QE, QV);
            else {
                add(node << 1, S, M, QS, M, QV);
                add(node << 1 | 1, M + 1, E, M + 1, QE, QV);
            }
            combine(V[node], V[node << 1], V[node << 1 | 1]);
        }
        public void set(int node, int S, int E, int QS, int QE, long QV) {
            if (QS <= S && E <= QE) {
                rset(node, QV);
                return;
            }
            push(node);
            int M = S + (E - S) / 2;
            if (QE <= M) set(node << 1, S, M, QS, QE, QV);
            else if (QS > M) set(node << 1 | 1, M + 1, E, QS, QE, QV);
            else {
                set(node << 1, S, M, QS, M, QV);
                set(node << 1 | 1, M + 1, E, M + 1, QE, QV);
            }
            combine(V[node], V[node << 1], V[node << 1 | 1]);
        }
    }

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
        public int nextInt() throws IOException {
            int ret = 0;
            Boolean flip = false;
            byte c = read();
            while (c < '0' || c > '9') {
                if (c == '-') flip = true;
                c = read();
            }
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            return flip ? -ret : ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) {
                buffer[0] = -1;
            }
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead) {
                fillBuffer();
            }
            return buffer[bufferPointer++];
        }
    }

    public static void main(String[] args) throws IOException {
        Reader reader = new Reader();
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = reader.nextInt();
        int Q = reader.nextInt();
        D = new long[300010];
        B = new long[300010];
        for (int a = 1; a <= N; ++a) {
            D[a] = reader.nextInt();
            B[a] = D[a] - D[a - 1];
        }
        SegmentTree root = new SegmentTree();
        root.build(1, 1, N);
        while (Q-- > 0) {
            int op = reader.nextInt();
            if (op == 1) {
                int L, R; long S, C;
                L = reader.nextInt(); R = reader.nextInt();
                S = reader.nextInt(); C = reader.nextInt();
                root.add(1, 1, N, L, L, S);
                if (L != R) root.add(1, 1, N, L + 1, R, C);
                if (R != N) root.add(1, 1, N, R + 1, R + 1, -(S + (R - L) * C));
            } else if (op == 2) {
                int L, R; long S, C;
                L = reader.nextInt(); R = reader.nextInt();
                S = reader.nextInt(); C = reader.nextInt();
                long old_sum = root.query(1, 1, N, L, R).sum;
                long prefix = (L == 1 ? 0 : root.query(1, 1, N, 1, L - 1).sum);
                root.set(1, 1, N, L, L, S - prefix);
                if (L != R) root.set(1, 1, N, L + 1, R, C);
                if (R != N) {
                    long new_sum = (S - prefix) + (R - L) * C;
                    root.add(1, 1, N, R + 1, R + 1, old_sum - new_sum);
                }
            } else {
                int L, R;
                L = reader.nextInt(); R = reader.nextInt();
                qval ret = root.query(1, 1, N, L, R);
                int len = Math.max(ret.prefix_len, ret.subarray_len + 1);
                len = Math.max(len, ret.suffix_len + 1);
                len = Math.min(len, ret.len);
                out.write(Integer.toString(len));
                out.write("\n");
            }
        }
        out.flush();
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2786 ms 139728 KB Output is correct
2 Correct 630 ms 79684 KB Output is correct
3 Correct 544 ms 79760 KB Output is correct
4 Correct 672 ms 80624 KB Output is correct
5 Correct 571 ms 81484 KB Output is correct
6 Correct 559 ms 79260 KB Output is correct
7 Correct 617 ms 79508 KB Output is correct
8 Correct 261 ms 70244 KB Output is correct
9 Correct 150 ms 70248 KB Output is correct
10 Correct 196 ms 70348 KB Output is correct
11 Correct 2662 ms 139744 KB Output is correct
12 Correct 2498 ms 141420 KB Output is correct
13 Correct 2089 ms 138040 KB Output is correct
14 Correct 1534 ms 135292 KB Output is correct
15 Correct 3066 ms 136340 KB Output is correct
16 Correct 2297 ms 140260 KB Output is correct
17 Correct 1999 ms 131480 KB Output is correct
18 Correct 2669 ms 137816 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 72704 KB Output is correct
2 Correct 194 ms 75796 KB Output is correct
3 Correct 147 ms 71168 KB Output is correct
4 Correct 180 ms 71576 KB Output is correct
5 Correct 251 ms 70200 KB Output is correct
6 Correct 182 ms 70264 KB Output is correct
7 Correct 119 ms 70352 KB Output is correct
8 Correct 164 ms 74424 KB Output is correct
9 Correct 154 ms 71148 KB Output is correct
10 Correct 193 ms 76912 KB Output is correct
11 Correct 163 ms 72976 KB Output is correct
12 Correct 181 ms 74496 KB Output is correct
13 Correct 289 ms 77940 KB Output is correct
14 Correct 150 ms 73060 KB Output is correct
15 Correct 165 ms 73360 KB Output is correct
16 Correct 152 ms 71324 KB Output is correct
17 Correct 257 ms 73372 KB Output is correct
18 Correct 151 ms 70668 KB Output is correct
19 Correct 250 ms 73628 KB Output is correct
20 Correct 186 ms 72848 KB Output is correct
21 Correct 323 ms 72936 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2554 ms 169796 KB Output is correct
2 Correct 460 ms 90452 KB Output is correct
3 Correct 463 ms 79240 KB Output is correct
4 Correct 377 ms 77128 KB Output is correct
5 Correct 440 ms 91156 KB Output is correct
6 Correct 477 ms 91844 KB Output is correct
7 Correct 443 ms 92020 KB Output is correct
8 Correct 129 ms 70220 KB Output is correct
9 Correct 136 ms 70456 KB Output is correct
10 Correct 160 ms 70376 KB Output is correct
11 Correct 3114 ms 174528 KB Output is correct
12 Correct 2903 ms 170572 KB Output is correct
13 Correct 2694 ms 174668 KB Output is correct
14 Correct 3107 ms 175772 KB Output is correct
15 Correct 2441 ms 170232 KB Output is correct
16 Correct 2305 ms 172864 KB Output is correct
17 Correct 2899 ms 175732 KB Output is correct
18 Correct 2305 ms 174900 KB Output is correct
19 Correct 1844 ms 166852 KB Output is correct
20 Correct 2228 ms 170008 KB Output is correct
21 Correct 2697 ms 167808 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3365 ms 179660 KB Output is correct
2 Correct 491 ms 77620 KB Output is correct
3 Correct 549 ms 79024 KB Output is correct
4 Correct 513 ms 78940 KB Output is correct
5 Correct 498 ms 79536 KB Output is correct
6 Correct 504 ms 79244 KB Output is correct
7 Correct 542 ms 79212 KB Output is correct
8 Correct 164 ms 70404 KB Output is correct
9 Correct 141 ms 70264 KB Output is correct
10 Correct 195 ms 70252 KB Output is correct
11 Correct 3788 ms 189176 KB Output is correct
12 Correct 3708 ms 175860 KB Output is correct
13 Correct 3178 ms 178720 KB Output is correct
14 Correct 3618 ms 177968 KB Output is correct
15 Correct 3380 ms 174176 KB Output is correct
16 Correct 3526 ms 180896 KB Output is correct
17 Correct 3151 ms 179768 KB Output is correct
18 Correct 3161 ms 185916 KB Output is correct
19 Correct 2776 ms 174712 KB Output is correct
20 Correct 3681 ms 173684 KB Output is correct
21 Correct 3534 ms 177272 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2554 ms 169796 KB Output is correct
2 Correct 460 ms 90452 KB Output is correct
3 Correct 463 ms 79240 KB Output is correct
4 Correct 377 ms 77128 KB Output is correct
5 Correct 440 ms 91156 KB Output is correct
6 Correct 477 ms 91844 KB Output is correct
7 Correct 443 ms 92020 KB Output is correct
8 Correct 129 ms 70220 KB Output is correct
9 Correct 136 ms 70456 KB Output is correct
10 Correct 160 ms 70376 KB Output is correct
11 Correct 3114 ms 174528 KB Output is correct
12 Correct 2903 ms 170572 KB Output is correct
13 Correct 2694 ms 174668 KB Output is correct
14 Correct 3107 ms 175772 KB Output is correct
15 Correct 2441 ms 170232 KB Output is correct
16 Correct 2305 ms 172864 KB Output is correct
17 Correct 2899 ms 175732 KB Output is correct
18 Correct 2305 ms 174900 KB Output is correct
19 Correct 1844 ms 166852 KB Output is correct
20 Correct 2228 ms 170008 KB Output is correct
21 Correct 2697 ms 167808 KB Output is correct
22 Correct 3926 ms 178508 KB Output is correct
23 Correct 532 ms 78640 KB Output is correct
24 Correct 543 ms 78420 KB Output is correct
25 Correct 572 ms 78760 KB Output is correct
26 Correct 675 ms 78384 KB Output is correct
27 Correct 684 ms 77988 KB Output is correct
28 Correct 583 ms 78728 KB Output is correct
29 Correct 153 ms 70532 KB Output is correct
30 Correct 134 ms 70300 KB Output is correct
31 Correct 147 ms 70324 KB Output is correct
32 Correct 4195 ms 182640 KB Output is correct
33 Correct 4006 ms 163756 KB Output is correct
34 Correct 3799 ms 185244 KB Output is correct
35 Correct 2756 ms 183564 KB Output is correct
36 Correct 2809 ms 186832 KB Output is correct
37 Correct 3747 ms 187356 KB Output is correct
38 Correct 3546 ms 184788 KB Output is correct
39 Correct 3964 ms 177904 KB Output is correct
40 Correct 4233 ms 186348 KB Output is correct
41 Correct 2796 ms 180088 KB Output is correct
42 Correct 4329 ms 183240 KB Output is correct
43 Correct 3736 ms 174620 KB Output is correct
44 Correct 3429 ms 170548 KB Output is correct
45 Correct 4041 ms 180388 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2786 ms 139728 KB Output is correct
2 Correct 630 ms 79684 KB Output is correct
3 Correct 544 ms 79760 KB Output is correct
4 Correct 672 ms 80624 KB Output is correct
5 Correct 571 ms 81484 KB Output is correct
6 Correct 559 ms 79260 KB Output is correct
7 Correct 617 ms 79508 KB Output is correct
8 Correct 261 ms 70244 KB Output is correct
9 Correct 150 ms 70248 KB Output is correct
10 Correct 196 ms 70348 KB Output is correct
11 Correct 2662 ms 139744 KB Output is correct
12 Correct 2498 ms 141420 KB Output is correct
13 Correct 2089 ms 138040 KB Output is correct
14 Correct 1534 ms 135292 KB Output is correct
15 Correct 3066 ms 136340 KB Output is correct
16 Correct 2297 ms 140260 KB Output is correct
17 Correct 1999 ms 131480 KB Output is correct
18 Correct 2669 ms 137816 KB Output is correct
19 Correct 188 ms 72704 KB Output is correct
20 Correct 194 ms 75796 KB Output is correct
21 Correct 147 ms 71168 KB Output is correct
22 Correct 180 ms 71576 KB Output is correct
23 Correct 251 ms 70200 KB Output is correct
24 Correct 182 ms 70264 KB Output is correct
25 Correct 119 ms 70352 KB Output is correct
26 Correct 164 ms 74424 KB Output is correct
27 Correct 154 ms 71148 KB Output is correct
28 Correct 193 ms 76912 KB Output is correct
29 Correct 163 ms 72976 KB Output is correct
30 Correct 181 ms 74496 KB Output is correct
31 Correct 289 ms 77940 KB Output is correct
32 Correct 150 ms 73060 KB Output is correct
33 Correct 165 ms 73360 KB Output is correct
34 Correct 152 ms 71324 KB Output is correct
35 Correct 257 ms 73372 KB Output is correct
36 Correct 151 ms 70668 KB Output is correct
37 Correct 250 ms 73628 KB Output is correct
38 Correct 186 ms 72848 KB Output is correct
39 Correct 323 ms 72936 KB Output is correct
40 Correct 2554 ms 169796 KB Output is correct
41 Correct 460 ms 90452 KB Output is correct
42 Correct 463 ms 79240 KB Output is correct
43 Correct 377 ms 77128 KB Output is correct
44 Correct 440 ms 91156 KB Output is correct
45 Correct 477 ms 91844 KB Output is correct
46 Correct 443 ms 92020 KB Output is correct
47 Correct 129 ms 70220 KB Output is correct
48 Correct 136 ms 70456 KB Output is correct
49 Correct 160 ms 70376 KB Output is correct
50 Correct 3114 ms 174528 KB Output is correct
51 Correct 2903 ms 170572 KB Output is correct
52 Correct 2694 ms 174668 KB Output is correct
53 Correct 3107 ms 175772 KB Output is correct
54 Correct 2441 ms 170232 KB Output is correct
55 Correct 2305 ms 172864 KB Output is correct
56 Correct 2899 ms 175732 KB Output is correct
57 Correct 2305 ms 174900 KB Output is correct
58 Correct 1844 ms 166852 KB Output is correct
59 Correct 2228 ms 170008 KB Output is correct
60 Correct 2697 ms 167808 KB Output is correct
61 Correct 3365 ms 179660 KB Output is correct
62 Correct 491 ms 77620 KB Output is correct
63 Correct 549 ms 79024 KB Output is correct
64 Correct 513 ms 78940 KB Output is correct
65 Correct 498 ms 79536 KB Output is correct
66 Correct 504 ms 79244 KB Output is correct
67 Correct 542 ms 79212 KB Output is correct
68 Correct 164 ms 70404 KB Output is correct
69 Correct 141 ms 70264 KB Output is correct
70 Correct 195 ms 70252 KB Output is correct
71 Correct 3788 ms 189176 KB Output is correct
72 Correct 3708 ms 175860 KB Output is correct
73 Correct 3178 ms 178720 KB Output is correct
74 Correct 3618 ms 177968 KB Output is correct
75 Correct 3380 ms 174176 KB Output is correct
76 Correct 3526 ms 180896 KB Output is correct
77 Correct 3151 ms 179768 KB Output is correct
78 Correct 3161 ms 185916 KB Output is correct
79 Correct 2776 ms 174712 KB Output is correct
80 Correct 3681 ms 173684 KB Output is correct
81 Correct 3534 ms 177272 KB Output is correct
82 Correct 3926 ms 178508 KB Output is correct
83 Correct 532 ms 78640 KB Output is correct
84 Correct 543 ms 78420 KB Output is correct
85 Correct 572 ms 78760 KB Output is correct
86 Correct 675 ms 78384 KB Output is correct
87 Correct 684 ms 77988 KB Output is correct
88 Correct 583 ms 78728 KB Output is correct
89 Correct 153 ms 70532 KB Output is correct
90 Correct 134 ms 70300 KB Output is correct
91 Correct 147 ms 70324 KB Output is correct
92 Correct 4195 ms 182640 KB Output is correct
93 Correct 4006 ms 163756 KB Output is correct
94 Correct 3799 ms 185244 KB Output is correct
95 Correct 2756 ms 183564 KB Output is correct
96 Correct 2809 ms 186832 KB Output is correct
97 Correct 3747 ms 187356 KB Output is correct
98 Correct 3546 ms 184788 KB Output is correct
99 Correct 3964 ms 177904 KB Output is correct
100 Correct 4233 ms 186348 KB Output is correct
101 Correct 2796 ms 180088 KB Output is correct
102 Correct 4329 ms 183240 KB Output is correct
103 Correct 3736 ms 174620 KB Output is correct
104 Correct 3429 ms 170548 KB Output is correct
105 Correct 4041 ms 180388 KB Output is correct
106 Correct 4803 ms 208864 KB Output is correct
107 Correct 1444 ms 109652 KB Output is correct
108 Correct 881 ms 100260 KB Output is correct
109 Correct 1203 ms 105532 KB Output is correct
110 Correct 125 ms 70196 KB Output is correct
111 Correct 130 ms 70376 KB Output is correct
112 Correct 209 ms 70244 KB Output is correct
113 Correct 4162 ms 182372 KB Output is correct
114 Correct 4185 ms 176608 KB Output is correct
115 Correct 3594 ms 176608 KB Output is correct
116 Correct 3870 ms 179144 KB Output is correct
117 Correct 4584 ms 203692 KB Output is correct
118 Correct 4078 ms 170080 KB Output is correct
119 Correct 4174 ms 177336 KB Output is correct
120 Correct 2678 ms 173704 KB Output is correct
121 Correct 3032 ms 174996 KB Output is correct
122 Correct 2794 ms 174828 KB Output is correct
123 Correct 1720 ms 168188 KB Output is correct
124 Correct 2882 ms 171172 KB Output is correct
125 Correct 2968 ms 170632 KB Output is correct
126 Correct 4946 ms 202488 KB Output is correct
127 Execution timed out 5150 ms 206800 KB Time limit exceeded
128 Halted 0 ms 0 KB -