Submission #381264

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
381264	2021-03-25T00:21:44 Z	ScarletS	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	382 ms	108692 KB

apple

#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct implicit
{
    struct node
    {
        node *l,*r;
        int val = 0;
        bool allSet = 0;
    };
    deque<node> buffer;
    int n;
    node *root;
    node *newnode()
    {
        buffer.emplace_back();
        return &buffer.back();
    }
    implicit(int n) : n(n) {root=newnode();}
    void passDown(node *&v)
    {
        if (!(v->l))
            v->l=newnode();
        if (!(v->r))
            v->r=newnode();
        if (v->allSet)
        {
            v->l->allSet=1;
            v->r->allSet=1;
        }
    }
    int calc(node *&v, int l, int r)
    {
        if (v->allSet)
            return r-l+1;
        return v->val;
    }
    void update(node *&v, int cL, int cR, int l, int r)
    {
        if (r<cL||cR<l)
            return;
        if (l<=cL&&cR<=r)
        {
            v->allSet=1;
            return;
        }
        passDown(v);
        update(v->l,cL,cL+(cR-cL)/2,l,r);
        update(v->r,cL+(cR-cL)/2+1,cR,l,r);
        v->val=calc(v->l,cL,cL+(cR-cL)/2)+calc(v->r,cL+(cR-cL)/2+1,cR);
    }
    void update(int l, int r)
    {
        update(root,1,n,l,r);
    }
    int query(node *&v, int cL, int cR, int l, int r)
    {
        if (r<cL||cR<l)
            return 0;
        if (l<=cL&&cR<=r)
            return calc(v,cL,cR);
        passDown(v);
        int rtn = query(v->l,cL,cL+(cR-cL)/2,l,r) + query(v->r,cL+(cR-cL)/2+1,cR,l,r);
        v->val=calc(v->l,cL,cL+(cR-cL)/2)+calc(v->r,cL+(cR-cL)/2+1,cR);
        return rtn;
    }
    int query(int l, int r)
    {
        return query(root,1,n,l,r);
    }
};

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,d,x,y,c=0;
    cin>>n;
    implicit seg(1e9);
    while (n--)
    {
        cin>>d>>x>>y;
        if (d==1)
        {
            c=seg.query(x+c,y+c);
            cout<<c<<"\n";
        }
        else
            seg.update(x+c,y+c);
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	17 ms	2796 KB	Output is correct
5	Correct	18 ms	3436 KB	Output is correct
6	Correct	18 ms	3320 KB	Output is correct
7	Correct	17 ms	3436 KB	Output is correct
8	Correct	117 ms	23712 KB	Output is correct
9	Correct	248 ms	41176 KB	Output is correct
10	Correct	262 ms	45272 KB	Output is correct
11	Correct	272 ms	48612 KB	Output is correct
12	Correct	273 ms	50240 KB	Output is correct
13	Correct	273 ms	58404 KB	Output is correct
14	Correct	255 ms	59376 KB	Output is correct
15	Correct	381 ms	105748 KB	Output is correct
16	Correct	382 ms	106356 KB	Output is correct
17	Correct	264 ms	60832 KB	Output is correct
18	Correct	252 ms	60752 KB	Output is correct
19	Correct	369 ms	108692 KB	Output is correct
20	Correct	373 ms	108692 KB	Output is correct