제출 #502406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
502406		daisy	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	315 ms	159844 KiB

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 / 100