oj.uz

Submission #502396

# Submission time Handle Problem Language Result Execution time Memory
502396 2022-01-05T21:31:41 Z daisy Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 102 ms 262148 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
long long m,num=1;
struct str
{
    long long lkid,rkid,lazy,sum;
    str()
    {
        lkid=rkid=lazy=sum=0;
    }

}tree[50000005];
void update(long long node,long long l,long long r,long long le,long long 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;
    }

    long long 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;
}
long long query(long long node,long long l,long long r,long long le,long long 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;
    }
    long long mid=(l+r)/2;

    long long 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;

    long long t,a,b,c=0;

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

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

}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 102 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -