Submission #1191214

#TimeUsernameProblemLanguageResultExecution timeMemory
1191214AliHasanli원숭이와 사과 나무 (IZhO12_apple)C++17
100 / 100
342 ms137396 KiB
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int val;
    node *l;
    node *r;
    node()
    {
        l=NULL;
        r=NULL;
        val=0;
    }
    void c()
    {
        if(l==NULL)
            l=new node();
        if(r==NULL)
            r=new node();
    }
};
node* root=new node();
void update(node *root,int l,int r,int ql,int qr)
{
    int mid=(l+r)/2;
    if(l>r || ql>qr || l>qr || ql>r)
        return;
    if(ql<=l && r<=qr)
    {
        root->val=(r-l+1);
        return;
    }
    root->c();
    if(root->val==r-l+1)
        root->l->val=mid-l+1,
        root->r->val=r-mid;
    update(root->l,l,mid,ql,qr);
    update(root->r,mid+1,r,ql,qr);
    root->val=root->l->val+root->r->val;
}
int query(node* root,int l,int r,int ql,int qr)
{
    int mid=(l+r)/2;
    if(l>r || ql>qr || l>qr || ql>r)
        return 0;
    if(ql<=l && r<=qr)
        return root->val;
    root->c();
    if(root->val==r-l+1)
        root->l->val=mid-l+1,
        root->r->val=r-mid;
    return query(root->l,l,mid,ql,qr)+query(root->r,mid+1,r,ql,qr);
}
int main()
{
    int q,c=0;
    cin>>q;
    while(q--)
    {
        int d,l,r;
        cin>>d>>l>>r;
        if(l>r)
            swap(l,r);
        if(d==1)
            cout<<query(root,1,1000000000,l+c,r+c)<<endl,
            c=query(root,1,1000000000,l+c,r+c);
        else
            update(root,1,1000000000,l+c,r+c);
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...