Submission #381170

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
381170	2021-03-24T16:46:40 Z	ntabc05101	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	20 ms	7404 KB

apple

#include<bits/stdc++.h>

const int mx=10000;
const int log_mx=14;

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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3692 KB	Output is correct
2	Correct	3 ms	3564 KB	Output is correct
3	Correct	3 ms	3564 KB	Output is correct
4	Correct	15 ms	3820 KB	Output is correct
5	Correct	17 ms	3820 KB	Output is correct
6	Correct	17 ms	3948 KB	Output is correct
7	Correct	18 ms	3952 KB	Output is correct
8	Runtime error	20 ms	7404 KB	Execution killed with signal 11
9	Halted	0 ms	0 KB	-