Submission #381171

#	Time	Username	Problem	Language	Result	Execution time	Memory
381171		ntabc05101	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	403 ms	153452 KiB

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 (stderr)

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 / 100