Submission #877055

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
877055	2023-11-22T19:50:48 Z	iliyan98	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	178 ms	54600 KB

apple

#include<iostream>
#include<bits/stdc++.h>
#define MAXN 4000010
#define BIL 1000000010
using namespace std;
struct node
{
    int l,r;
    bool lazy;
    int sum;

    void newNode()
    {
        lazy=0; sum=0;
        l=-1;
        r=-1;
    }
};
int len=1;
node tree[MAXN];
void update(int ind, int l, int r, int ql, int qr)
{
    if(ql<=l && r<=qr)
    {
        tree[ind].lazy=1;
        return;
    }
    int mid=(l+r)/2;
    if(ql<=mid)
    {
        if(tree[ind].l==-1)
        {
            len++;
            tree[len].newNode();
            tree[ind].l=len;
        }
        update(tree[ind].l,l,mid,ql,qr);
    }
    if(qr>mid)
    {
        if(tree[ind].r==-1)
        {
            len++;
            tree[len].newNode();
            tree[ind].r=len;
        }
        update(tree[ind].r,mid+1,r,ql,qr);
    }
    tree[ind].sum=0;
    if (tree[ind].l!=-1) {
        if (tree[tree[ind].l].lazy==1) tree[ind].sum+=(mid-l+1);
        else tree[ind].sum+=tree[tree[ind].l].sum;
    }
    if (tree[ind].r!=-1) {
        if (tree[tree[ind].r].lazy==1) tree[ind].sum+=(r-(mid+1)+1);
        else tree[ind].sum+=tree[tree[ind].r].sum;
    }
}
int query(int ind, int l, int r, int ql, int qr, bool up)
{
    up|=tree[ind].lazy;
    if(ql<=l && r<=qr){
        if (up==true) return (r-l+1);
        return tree[ind].sum;
    }
    int mid=(l+r)/2;
    int val1=0,val2=0;
    if(ql<=mid)
    {
        if(tree[ind].l!=-1) val1= query(tree[ind].l,l,mid,ql,qr,up);
        else if(up>0)
        {
            len++;
            tree[len].newNode();
            tree[ind].l=len;
            val1= query(tree[ind].l,l,mid,ql,qr,up);
        }
    }
    if(qr>mid)
    {
        if(tree[ind].r!=-1)val2= query(tree[ind].r,mid+1,r,ql,qr,up);
        else if(up>0)
        {
            len++;
            tree[len].newNode();
            tree[ind].r=len;
            val2= query(tree[ind].r,mid+1,r,ql,qr,up);
        }
    }
    return val1+val2;
}
int main()
{
    int n,c=0;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    tree[1].newNode();
    for(int i=0;i<n;i++)
    {
        int d,x,y;
        cin>>d>>x>>y;
        if(d==2)
        {
            update(1,1,BIL,x+c,y+c);
        }
        else
        {
            int res=query(1,1,BIL,x+c,y+c,0);
            c=res;
            cout<<res<<"\n";
        }
    }
}
/*
3
2 5 8
2 7 10
1 1 10

4
2 2 3
1 1 3
2 2 3
1 -1 3

6
2 1 7
2 10 12
1 7 11
2 11 13
1 8 10
1 15 17

3
2 1 8
2 13 18
1 6 15
*/

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	6 ms	2776 KB	Output is correct
5	Correct	7 ms	2652 KB	Output is correct
6	Correct	10 ms	2652 KB	Output is correct
7	Correct	8 ms	2652 KB	Output is correct
8	Correct	53 ms	13792 KB	Output is correct
9	Correct	97 ms	23136 KB	Output is correct
10	Correct	109 ms	25180 KB	Output is correct
11	Correct	96 ms	25356 KB	Output is correct
12	Correct	106 ms	27220 KB	Output is correct
13	Correct	93 ms	31724 KB	Output is correct
14	Correct	101 ms	31996 KB	Output is correct
15	Correct	138 ms	54344 KB	Output is correct
16	Correct	178 ms	54560 KB	Output is correct
17	Correct	98 ms	31928 KB	Output is correct
18	Correct	111 ms	31824 KB	Output is correct
19	Correct	136 ms	54600 KB	Output is correct
20	Correct	134 ms	54480 KB	Output is correct