Submission #502403

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
502403	2022-01-05T21:37:33 Z	daisy	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	247 ms	160784 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,1000000000,a,b);
        }
        if(t==1)
        {
            c=query(1,1,1000000000,a,b);
            cout<<c<<endl;
        }
    }

}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	78496 KB	Output is correct
2	Correct	36 ms	78532 KB	Output is correct
3	Correct	37 ms	78540 KB	Output is correct
4	Correct	51 ms	78680 KB	Output is correct
5	Correct	56 ms	78636 KB	Output is correct
6	Correct	49 ms	78584 KB	Output is correct
7	Correct	49 ms	78596 KB	Output is correct
8	Correct	134 ms	78800 KB	Output is correct
9	Correct	247 ms	78908 KB	Output is correct
10	Correct	227 ms	80636 KB	Output is correct
11	Correct	247 ms	80776 KB	Output is correct
12	Correct	235 ms	80648 KB	Output is correct
13	Correct	210 ms	81016 KB	Output is correct
14	Correct	219 ms	81088 KB	Output is correct
15	Runtime error	218 ms	160784 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-