Submission #502394

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
502394	2022-01-05T21:30:18 Z	daisy	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	176 ms	80680 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[5000005];
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,4000005,a,b);
        }
        if(t==1)
        {
            c=query(1,1,4000005,a,b);
            cout<<c<<endl;
        }
    }

}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	78568 KB	Output is correct
2	Correct	32 ms	78488 KB	Output is correct
3	Correct	33 ms	78528 KB	Output is correct
4	Correct	42 ms	78656 KB	Output is correct
5	Correct	44 ms	78660 KB	Output is correct
6	Correct	44 ms	78768 KB	Output is correct
7	Correct	44 ms	78676 KB	Output is correct
8	Correct	112 ms	79556 KB	Output is correct
9	Incorrect	176 ms	80680 KB	Output isn't correct
10	Halted	0 ms	0 KB	-