Submission #502406

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
502406	2022-01-05T21:41:01 Z	daisy	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	315 ms	159844 KB

apple

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int m,num=1;
struct str
{
    int lkid,rkid,lazy,sum;
    str()
    {
        lkid=rkid=lazy=sum=0;
    }

}tree[10000005];
void update(int node,int l,int r,int le,int ri)
{
    if(!tree[node].lkid){num++;tree[node].lkid=num;}
    if(!tree[node].rkid){num++;tree[node].rkid=num;}
    if(tree[node].lazy)
    {
        tree[node].sum=(r-l+1);
        tree[tree[node].lkid].lazy=1;
        tree[tree[node].rkid].lazy=1;
        tree[node].lazy=0;
    }
    if(l>ri || r<le) return;
    if(l>=le && r<=ri)
    {
        tree[node].sum=(r-l+1);tree[node].lazy=1;
        return;
    }

    int mid=(l+r)/2;

    update(tree[node].lkid,l,mid,le,ri);
    update(tree[node].rkid,mid+1,r,le,ri);

    tree[node].sum=tree[tree[node].lkid].sum+tree[tree[node].rkid].sum;
}
int query(int node,int l,int r,int le,int ri)
{
    if(node==0) return 0;

    if(!tree[node].lkid){num++;tree[node].lkid=num;}
    if(!tree[node].rkid){num++;tree[node].rkid=num;}

    if(tree[node].lazy)
    {
        tree[node].sum=(r-l+1);
        tree[tree[node].lkid].lazy=1;
        tree[tree[node].rkid].lazy=1;
        tree[node].lazy=0;
    }
    if(l>ri || r<le) return 0;
    if(l>=le && r<=ri)
    {
        return tree[node].sum;
    }
    int mid=(l+r)/2;

    int r1=query(tree[node].lkid,l,mid,le,ri), r2=query(tree[node].rkid,mid+1,r,le,ri);
    tree[node].sum=tree[tree[node].lkid].sum+tree[tree[node].rkid].sum;

    return r1+r2;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    cin>>m;

    int t,a,b,c=0;

    for(int i=0;i<m;i++)
    {
        cin>>t>>a>>b;
        a+=c;b+=c;

        if(t==2)
        {
            update(1,1,1000000000,a,b);
        }
        if(t==1)
        {
            c=query(1,1,1000000000,a,b);
            cout<<c<<endl;
        }
    }

}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	156740 KB	Output is correct
2	Correct	69 ms	156852 KB	Output is correct
3	Correct	69 ms	156868 KB	Output is correct
4	Correct	77 ms	156776 KB	Output is correct
5	Correct	83 ms	156868 KB	Output is correct
6	Correct	82 ms	156832 KB	Output is correct
7	Correct	81 ms	156824 KB	Output is correct
8	Correct	160 ms	156980 KB	Output is correct
9	Correct	252 ms	157212 KB	Output is correct
10	Correct	271 ms	157148 KB	Output is correct
11	Correct	271 ms	157400 KB	Output is correct
12	Correct	257 ms	157232 KB	Output is correct
13	Correct	237 ms	157272 KB	Output is correct
14	Correct	241 ms	157364 KB	Output is correct
15	Correct	306 ms	158020 KB	Output is correct
16	Correct	315 ms	159844 KB	Output is correct
17	Correct	242 ms	159428 KB	Output is correct
18	Correct	244 ms	159428 KB	Output is correct
19	Correct	308 ms	159440 KB	Output is correct
20	Correct	309 ms	159428 KB	Output is correct