Submission #381171

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
381171	2021-03-24T16:47:28 Z	ntabc05101	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	403 ms	153452 KB

apple

#include<bits/stdc++.h>

const int mx=100000;
const int log_mx=64;

struct Node {
        int l=-1, r=-1, tl, tr, lazy=0, sum=0;
};

Node nodes[mx*log_mx+10];
int current=2;

void propagate(int node) {
        int mid=nodes[node].tl+nodes[node].tr>>1;
        if (nodes[node].l<0) {
                nodes[node].l=current;
                nodes[current].tl=nodes[node].tl;
                nodes[current].tr=mid;
                current++;
        }
        if (nodes[node].r<0) {
                nodes[node].r=current;
                nodes[current].tl=mid+1;
                nodes[current].tr=nodes[node].tr;
                current++;
        }

        if (!nodes[node].lazy) return ;

        nodes[nodes[node].l].sum=nodes[nodes[node].l].tr-nodes[nodes[node].l].tl+1;
        nodes[nodes[node].r].sum=nodes[nodes[node].r].tr-nodes[nodes[node].r].tl+1;
        nodes[nodes[node].l].lazy=nodes[nodes[node].r].lazy=1;
        nodes[node].lazy=0;
}

void update(int node, int l, int r) {
        //std::cout<<node<<" "<<nodes[node].tl<<" "<<nodes[node].tr<<"\n";
        if (l<=nodes[node].tl and r>=nodes[node].tr) {
                nodes[node].lazy=1;
                nodes[node].sum=nodes[node].tr-nodes[node].tl+1;
                return ;
        }

        propagate(node);
        if (nodes[nodes[node].l].tr>=l) update(nodes[node].l, l, r);
        if (nodes[nodes[node].r].tl<=r) update(nodes[node].r, l, r);

        nodes[node].sum=nodes[nodes[node].l].sum+nodes[nodes[node].r].sum;
}

int get(int node, int l, int r) {
        if (l<=nodes[node].tl and r>=nodes[node].tr) {
                return nodes[node].sum;
        }

        propagate(node);
        return (nodes[nodes[node].l].tr>=l ? get(nodes[node].l, l, r): 0) + 
                (nodes[nodes[node].r].tl<=r ? get(nodes[node].r, l, r): 0);
}

int main() {
        std::ios_base::sync_with_stdio(0); std::cin.tie(0);

        int m; std::cin>>m;

        nodes[1].sum=nodes[1].lazy=0;
        nodes[1].tl=1, nodes[1].tr=1e9;

        int c=0;
        while (m--) {
                int type, left, right; std::cin>>type>>left>>right;

                //std::cout<<type<<" "<<left<<" "<<right<<"\n";
                if (type==1) {
                        c=get(1, left+c, right+c);
                        std::cout<<c<<"\n";
                }
                else {
                        update(1, left+c, right+c);
                }
        }
}

Compilation message

apple.cpp: In function 'void propagate(int)':
apple.cpp:14:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |         int mid=nodes[node].tl+nodes[node].tr>>1;
      |                 ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	150636 KB	Output is correct
2	Correct	92 ms	150636 KB	Output is correct
3	Correct	93 ms	150636 KB	Output is correct
4	Correct	105 ms	150636 KB	Output is correct
5	Correct	114 ms	150728 KB	Output is correct
6	Correct	108 ms	150636 KB	Output is correct
7	Correct	110 ms	150764 KB	Output is correct
8	Correct	201 ms	151596 KB	Output is correct
9	Correct	322 ms	152812 KB	Output is correct
10	Correct	343 ms	152940 KB	Output is correct
11	Correct	336 ms	152784 KB	Output is correct
12	Correct	324 ms	152868 KB	Output is correct
13	Correct	310 ms	153164 KB	Output is correct
14	Correct	311 ms	153260 KB	Output is correct
15	Correct	401 ms	153356 KB	Output is correct
16	Correct	381 ms	153324 KB	Output is correct
17	Correct	305 ms	153260 KB	Output is correct
18	Correct	304 ms	153276 KB	Output is correct
19	Correct	400 ms	153452 KB	Output is correct
20	Correct	403 ms	153372 KB	Output is correct