oj.uz

Submission #255292

# Submission time Handle Problem Language Result Execution time Memory
255292 2020-07-31T17:09:06 Z model_code Progression (NOI20_progression) Java 11
59 / 100
 5000 ms 194224 KB 
import java.io.DataInputStream;
import java.io.IOException;
import java.io.PrintStream;
import java.io.BufferedOutputStream;

public class Progression {
    private 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;
        }
        public long nextLong() throws IOException {
            long 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++];
        }
    }
    
    private static class Node {
        long left_s, left_c, right_s, right_c;
        int left_len, right_len, curr_len;
        boolean is_override;
        long push_s, push_c;
    }
    
    private static final int DEPTH = 19;
    private static Node[] stree = new Node[1<<(DEPTH+1)];
    private static void construct(int i) {
        final Node me = stree[i], left = stree[i<<1], right = stree[(i<<1)+1];
        final int mylen = 1<<(Integer.numberOfLeadingZeros(i)-(31-DEPTH));
        final int childlen = mylen>>1;
        
        if(childlen==1) {
            right.right_c=left.left_c=right.left_c=left.right_c=right.left_s-left.right_s;
        }
        me.curr_len=Math.max(left.curr_len,right.curr_len);
        int lmergelen =
            (right.left_s - left.right_s == left.right_c)
                ? ((right.left_c == left.right_c) ? right.left_len : 1)
                : 0;
        int rmergelen =
            (right.left_s - left.right_s == right.left_c)
                ? ((right.left_c == left.right_c) ? left.right_len : 1)
                : 0;
        me.curr_len = Math.max(me.curr_len, Math.max(left.right_len + lmergelen, right.left_len + rmergelen));
        me.left_s = left.left_s;
        me.left_c = left.left_c;
        if(left.left_len == childlen) me.left_len = childlen + lmergelen;
        else me.left_len = left.left_len;
        me.right_s = right.right_s;
        me.right_c = right.right_c;
        if(right.right_len == childlen) me.right_len = childlen + rmergelen;
        else me.right_len = right.right_len;
    }
    private static void pushdown(int i){
        final Node me = stree[i];
        if(me.is_override||me.push_s!=0||me.push_c!=0){
            Node left=stree[i<<1];
            Node right=stree[(i<<1)+1];
            final int mylen = 1 << (Integer.numberOfLeadingZeros(i) - (31 - DEPTH));
            final int childlen = mylen >> 1;

            if(me.is_override){
                me.is_override=false;
                left.curr_len=childlen;
                left.left_s=me.push_s;
                left.left_c=me.push_c;
                left.left_len=childlen;
                left.right_s=me.push_s+me.push_c*(childlen-1);
                left.right_c=me.push_c;
                left.right_len=childlen;
                left.push_s=me.push_s;
                left.push_c=me.push_c;
                left.is_override=true;
                final long tmp_s=me.push_s+me.push_c*childlen;
                right.curr_len=childlen;
                right.left_s=tmp_s;
                right.left_c=me.push_c;
                right.left_len=childlen;
                right.right_s=tmp_s+me.push_c*(childlen-1);
                right.right_c=me.push_c;
                right.right_len=childlen;
                right.push_s=tmp_s;
                right.push_c=me.push_c;
                right.is_override=true;
            }
            else{
                left.left_s+=me.push_s;
                left.left_c+=me.push_c;
                left.right_s+=me.push_s+me.push_c*(childlen-1);
                left.right_c+=me.push_c;
                left.push_s+=me.push_s;
                left.push_c+=me.push_c;
                final long tmp_s=me.push_s+me.push_c*childlen;
                right.left_s+=tmp_s;
                right.left_c+=me.push_c;
                right.right_s+=tmp_s+me.push_c*(childlen-1);
                right.right_c+=me.push_c;
                right.push_s+=tmp_s;
                right.push_c+=me.push_c;
            }
            me.push_s=0;
            me.push_c=0;
        }
    }
    private static void increment(int i, int l, int r, long s, int c){
        final Node me = stree[i];
        final int mylen = 1 << (Integer.numberOfLeadingZeros(i) - (31 - DEPTH));
        final int childlen = mylen >> 1;

        if(l==0&&r==mylen) {
            me.left_s += s;
            me.left_c += c;
            me.right_s += s + (long)(c) * (mylen - 1);
            me.right_c += c;
            me.push_s += s;
            me.push_c += c;
            return;
        }
        pushdown(i);
        if (l<childlen) increment(i<<1, l, Math.min(r,childlen), s, c);
        if (r>childlen) increment((i<<1)+1, Math.max(l-childlen,0), r-childlen, s+(long)(c)*Math.max(childlen - l, 0), c);
        construct(i);
    }
    private static void overwrite(int i, int l, int r, long s, int c){
        final Node me = stree[i];
        final int mylen = 1 << (Integer.numberOfLeadingZeros(i) - (31 - DEPTH));
        final int childlen = mylen >> 1;

        if(l==0&&r==mylen) {
            me.curr_len = mylen;
            me.left_s = s;
            me.left_c = c;
            me.left_len = mylen;
            me.right_s = s + (long)(c) * (mylen - 1);
            me.right_c = c;
            me.right_len = mylen;
            me.push_s = s;
            me.push_c = c;
            me.is_override = true;
            return;
        }
        pushdown(i);
        if (l<childlen) overwrite(i<<1, l, Math.min(r,childlen), s, c);
        if (r>childlen) overwrite((i<<1)+1, Math.max(l-childlen,0), r-childlen, s+(long)(c)*Math.max(childlen - l, 0), c);
        construct(i);
    }
    private static int query(int i, int l, int r){
        final Node me = stree[i];
        final int mylen = 1 << (Integer.numberOfLeadingZeros(i) - (31 - DEPTH));
        final int childlen = mylen >> 1;

        if(l==0&&r==mylen) {
            return me.curr_len;
        }
        final Node left=stree[i<<1];
        final Node right=stree[(i<<1)+1];
        pushdown(i);
        int ans = 0;
        if (l<childlen) ans = Math.max(ans, query(i<<1, l, Math.min(r,childlen)));
        if (r>childlen) ans = Math.max(ans, query((i<<1)+1, Math.max(l-childlen,0), r-childlen));
        if (l<childlen && r>childlen) {
            ans = Math.max(2, ans);
            int lmergelen =
                (right.left_s - left.right_s == left.right_c)
                    ? ((right.left_c == left.right_c) ? Math.min(r-childlen,right.left_len) : 1)
                    : 0;
            int rmergelen =
                (right.left_s - left.right_s == right.left_c)
                    ? ((right.left_c == left.right_c) ? Math.min(childlen-l,left.right_len) : 1)
                    : 0;
            ans = Math.max(ans, Math.max(Math.min(childlen-l,left.right_len) + lmergelen, Math.min(r-childlen,right.left_len) + rmergelen));
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        for(int i=0;i<(1<<(DEPTH+1));++i)stree[i]=new Node();
        Reader reader = new Reader();
        PrintStream out = new PrintStream(new BufferedOutputStream(System.out));
        
        final int n = reader.nextInt();
        final int q = reader.nextInt();
        for (int i=0;i<n;++i){
            stree[(1 << DEPTH) + i].push_s = reader.nextInt();
        }
        for (int i=0;i<(1<<DEPTH);++i){
            stree[(1 << DEPTH) + i].is_override = true;
            stree[(1 << DEPTH) + i].curr_len = 1;
            stree[(1 << DEPTH) + i].left_s = stree[(1 << DEPTH) + i].push_s;
            stree[(1 << DEPTH) + i].left_len = 1;
            stree[(1 << DEPTH) + i].right_s = stree[(1 << DEPTH) + i].push_s;
            stree[(1 << DEPTH) + i].right_len = 1;
        }
        for(int i = (1<<DEPTH) - 1; i > 0; --i){
            construct(i);
        }
        for(int i=0;i<q;++i){
            final int type = reader.nextInt();
            if(type==1){
                final int l=reader.nextInt();
                final int r=reader.nextInt();
                final int s=reader.nextInt();
                final int c=reader.nextInt();
                increment(1, l-1, r, s, c);
            }
            else if(type==2){
                final int l=reader.nextInt();
                final int r=reader.nextInt();
                final int s=reader.nextInt();
                final int c=reader.nextInt();
                overwrite(1, l-1, r, s, c);
            }
            else if(type==3){
                final int l=reader.nextInt();
                final int r=reader.nextInt();
                out.print(query(1, l-1, r));
                out.print('\n');
            }
        }
        
        out.flush(); // remember to flush just once, at the very end of your program
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1658 ms 139208 KB Output is correct
2 Correct 3794 ms 146860 KB Output is correct
3 Correct 3623 ms 147140 KB Output is correct
4 Correct 3784 ms 147608 KB Output is correct
5 Correct 3631 ms 143760 KB Output is correct
6 Correct 3746 ms 143392 KB Output is correct
7 Correct 3545 ms 143040 KB Output is correct
8 Correct 2007 ms 129316 KB Output is correct
9 Correct 2143 ms 133436 KB Output is correct
10 Correct 3045 ms 128580 KB Output is correct
11 Correct 3325 ms 152640 KB Output is correct
12 Correct 3788 ms 147232 KB Output is correct
13 Correct 4606 ms 156936 KB Output is correct
14 Correct 3656 ms 149120 KB Output is correct
15 Correct 3773 ms 151104 KB Output is correct
16 Correct 3645 ms 154492 KB Output is correct
17 Correct 3447 ms 144420 KB Output is correct
18 Correct 2895 ms 144028 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2435 ms 129784 KB Output is correct
2 Correct 3139 ms 134504 KB Output is correct
3 Correct 2670 ms 130632 KB Output is correct
4 Correct 2814 ms 134788 KB Output is correct
5 Correct 2718 ms 129600 KB Output is correct
6 Correct 2527 ms 130424 KB Output is correct
7 Correct 3278 ms 129684 KB Output is correct
8 Correct 2501 ms 133896 KB Output is correct
9 Correct 3047 ms 132452 KB Output is correct
10 Correct 2704 ms 131864 KB Output is correct
11 Correct 1903 ms 128348 KB Output is correct
12 Correct 2486 ms 133500 KB Output is correct
13 Correct 2648 ms 134108 KB Output is correct
14 Correct 2604 ms 133416 KB Output is correct
15 Correct 3191 ms 133336 KB Output is correct
16 Correct 2587 ms 130412 KB Output is correct
17 Correct 2724 ms 134764 KB Output is correct
18 Correct 3124 ms 135888 KB Output is correct
19 Correct 2859 ms 134624 KB Output is correct
20 Correct 2581 ms 133160 KB Output is correct
21 Correct 3245 ms 130336 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3934 ms 187020 KB Output is correct
2 Correct 3873 ms 186052 KB Output is correct
3 Correct 2725 ms 184720 KB Output is correct
4 Correct 2635 ms 185488 KB Output is correct
5 Correct 3035 ms 185268 KB Output is correct
6 Correct 4008 ms 184440 KB Output is correct
7 Correct 3525 ms 185852 KB Output is correct
8 Correct 2616 ms 129244 KB Output is correct
9 Correct 2543 ms 129036 KB Output is correct
10 Correct 2719 ms 133556 KB Output is correct
11 Correct 3764 ms 186752 KB Output is correct
12 Correct 3026 ms 185948 KB Output is correct
13 Correct 4116 ms 186036 KB Output is correct
14 Correct 3968 ms 191692 KB Output is correct
15 Correct 3960 ms 186772 KB Output is correct
16 Correct 4130 ms 187280 KB Output is correct
17 Correct 4078 ms 186740 KB Output is correct
18 Correct 3628 ms 194224 KB Output is correct
19 Correct 4041 ms 185816 KB Output is correct
20 Correct 4094 ms 185664 KB Output is correct
21 Correct 3858 ms 185292 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4086 ms 149320 KB Output is correct
2 Correct 3982 ms 146944 KB Output is correct
3 Correct 3917 ms 147788 KB Output is correct
4 Correct 3435 ms 137304 KB Output is correct
5 Correct 3398 ms 153820 KB Output is correct
6 Correct 3168 ms 136208 KB Output is correct
7 Correct 4336 ms 148624 KB Output is correct
8 Correct 3605 ms 130408 KB Output is correct
9 Correct 2760 ms 129172 KB Output is correct
10 Correct 2732 ms 130184 KB Output is correct
11 Correct 3449 ms 143452 KB Output is correct
12 Correct 4253 ms 145212 KB Output is correct
13 Correct 4464 ms 148536 KB Output is correct
14 Correct 4322 ms 145920 KB Output is correct
15 Correct 4374 ms 149120 KB Output is correct
16 Correct 4520 ms 157132 KB Output is correct
17 Correct 4117 ms 148920 KB Output is correct
18 Correct 4115 ms 147744 KB Output is correct
19 Correct 4291 ms 149384 KB Output is correct
20 Execution timed out 5095 ms 136400 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3934 ms 187020 KB Output is correct
2 Correct 3873 ms 186052 KB Output is correct
3 Correct 2725 ms 184720 KB Output is correct
4 Correct 2635 ms 185488 KB Output is correct
5 Correct 3035 ms 185268 KB Output is correct
6 Correct 4008 ms 184440 KB Output is correct
7 Correct 3525 ms 185852 KB Output is correct
8 Correct 2616 ms 129244 KB Output is correct
9 Correct 2543 ms 129036 KB Output is correct
10 Correct 2719 ms 133556 KB Output is correct
11 Correct 3764 ms 186752 KB Output is correct
12 Correct 3026 ms 185948 KB Output is correct
13 Correct 4116 ms 186036 KB Output is correct
14 Correct 3968 ms 191692 KB Output is correct
15 Correct 3960 ms 186772 KB Output is correct
16 Correct 4130 ms 187280 KB Output is correct
17 Correct 4078 ms 186740 KB Output is correct
18 Correct 3628 ms 194224 KB Output is correct
19 Correct 4041 ms 185816 KB Output is correct
20 Correct 4094 ms 185664 KB Output is correct
21 Correct 3858 ms 185292 KB Output is correct
22 Correct 3639 ms 143688 KB Output is correct
23 Correct 4067 ms 146184 KB Output is correct
24 Correct 3445 ms 143600 KB Output is correct
25 Correct 2991 ms 144444 KB Output is correct
26 Correct 4206 ms 148160 KB Output is correct
27 Correct 2872 ms 143928 KB Output is correct
28 Correct 2457 ms 142980 KB Output is correct
29 Correct 2912 ms 131432 KB Output is correct
30 Correct 2817 ms 128484 KB Output is correct
31 Correct 2205 ms 127532 KB Output is correct
32 Correct 3351 ms 147204 KB Output is correct
33 Correct 3842 ms 149928 KB Output is correct
34 Correct 3100 ms 144072 KB Output is correct
35 Correct 3456 ms 147064 KB Output is correct
36 Correct 3338 ms 162320 KB Output is correct
37 Correct 3210 ms 157512 KB Output is correct
38 Correct 4767 ms 156376 KB Output is correct
39 Execution timed out 5019 ms 141616 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1658 ms 139208 KB Output is correct
2 Correct 3794 ms 146860 KB Output is correct
3 Correct 3623 ms 147140 KB Output is correct
4 Correct 3784 ms 147608 KB Output is correct
5 Correct 3631 ms 143760 KB Output is correct
6 Correct 3746 ms 143392 KB Output is correct
7 Correct 3545 ms 143040 KB Output is correct
8 Correct 2007 ms 129316 KB Output is correct
9 Correct 2143 ms 133436 KB Output is correct
10 Correct 3045 ms 128580 KB Output is correct
11 Correct 3325 ms 152640 KB Output is correct
12 Correct 3788 ms 147232 KB Output is correct
13 Correct 4606 ms 156936 KB Output is correct
14 Correct 3656 ms 149120 KB Output is correct
15 Correct 3773 ms 151104 KB Output is correct
16 Correct 3645 ms 154492 KB Output is correct
17 Correct 3447 ms 144420 KB Output is correct
18 Correct 2895 ms 144028 KB Output is correct
19 Correct 2435 ms 129784 KB Output is correct
20 Correct 3139 ms 134504 KB Output is correct
21 Correct 2670 ms 130632 KB Output is correct
22 Correct 2814 ms 134788 KB Output is correct
23 Correct 2718 ms 129600 KB Output is correct
24 Correct 2527 ms 130424 KB Output is correct
25 Correct 3278 ms 129684 KB Output is correct
26 Correct 2501 ms 133896 KB Output is correct
27 Correct 3047 ms 132452 KB Output is correct
28 Correct 2704 ms 131864 KB Output is correct
29 Correct 1903 ms 128348 KB Output is correct
30 Correct 2486 ms 133500 KB Output is correct
31 Correct 2648 ms 134108 KB Output is correct
32 Correct 2604 ms 133416 KB Output is correct
33 Correct 3191 ms 133336 KB Output is correct
34 Correct 2587 ms 130412 KB Output is correct
35 Correct 2724 ms 134764 KB Output is correct
36 Correct 3124 ms 135888 KB Output is correct
37 Correct 2859 ms 134624 KB Output is correct
38 Correct 2581 ms 133160 KB Output is correct
39 Correct 3245 ms 130336 KB Output is correct
40 Correct 3934 ms 187020 KB Output is correct
41 Correct 3873 ms 186052 KB Output is correct
42 Correct 2725 ms 184720 KB Output is correct
43 Correct 2635 ms 185488 KB Output is correct
44 Correct 3035 ms 185268 KB Output is correct
45 Correct 4008 ms 184440 KB Output is correct
46 Correct 3525 ms 185852 KB Output is correct
47 Correct 2616 ms 129244 KB Output is correct
48 Correct 2543 ms 129036 KB Output is correct
49 Correct 2719 ms 133556 KB Output is correct
50 Correct 3764 ms 186752 KB Output is correct
51 Correct 3026 ms 185948 KB Output is correct
52 Correct 4116 ms 186036 KB Output is correct
53 Correct 3968 ms 191692 KB Output is correct
54 Correct 3960 ms 186772 KB Output is correct
55 Correct 4130 ms 187280 KB Output is correct
56 Correct 4078 ms 186740 KB Output is correct
57 Correct 3628 ms 194224 KB Output is correct
58 Correct 4041 ms 185816 KB Output is correct
59 Correct 4094 ms 185664 KB Output is correct
60 Correct 3858 ms 185292 KB Output is correct
61 Correct 4086 ms 149320 KB Output is correct
62 Correct 3982 ms 146944 KB Output is correct
63 Correct 3917 ms 147788 KB Output is correct
64 Correct 3435 ms 137304 KB Output is correct
65 Correct 3398 ms 153820 KB Output is correct
66 Correct 3168 ms 136208 KB Output is correct
67 Correct 4336 ms 148624 KB Output is correct
68 Correct 3605 ms 130408 KB Output is correct
69 Correct 2760 ms 129172 KB Output is correct
70 Correct 2732 ms 130184 KB Output is correct
71 Correct 3449 ms 143452 KB Output is correct
72 Correct 4253 ms 145212 KB Output is correct
73 Correct 4464 ms 148536 KB Output is correct
74 Correct 4322 ms 145920 KB Output is correct
75 Correct 4374 ms 149120 KB Output is correct
76 Correct 4520 ms 157132 KB Output is correct
77 Correct 4117 ms 148920 KB Output is correct
78 Correct 4115 ms 147744 KB Output is correct
79 Correct 4291 ms 149384 KB Output is correct
80 Execution timed out 5095 ms 136400 KB Time limit exceeded
81 Halted 0 ms 0 KB -