Submission #768269

#	Time	Username	Problem	Language	Result	Execution time	Memory
768269		Ahmed57	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	616 ms	262144 KiB

apple

#include<bits/stdc++.h>

using namespace std;
//TRIE
struct node{
   node *nxt[2];
   int lzAdd = 0 , sum = 0;
   node(){
      lzAdd = 0 , sum = 0;
      for(int i = 0;i<2;i++){
        nxt[i] = NULL;
      }
   }
};
void prop(node *root,int l,int r){
    if(root->lzAdd==0)return ;
    root->sum=(r-l+1)*root->lzAdd;
    if(l!=r){
        if(root->nxt[0]==NULL)root->nxt[0] = new node();
        if(root->nxt[1]==NULL)root->nxt[1] = new node();
        root->nxt[0]->lzAdd=root->lzAdd;
        root->nxt[1]->lzAdd=root->lzAdd;
    }
    root->lzAdd = 0;
}
long long query(node *root,int l,int r,int lq,int rq){
    prop(root,l,r);
    if(l>=lq&&r<=rq)return root->sum;
    if(l>rq||r<lq)return 0;
    int md = (l+r)/2;
    long long p1 = 0 , p2 = 0;
    if(root->nxt[0]!=NULL)p1 = query(root->nxt[0],l,md,lq,rq);
    if(root->nxt[1]!=NULL)p2 = query(root->nxt[1],md+1,r,lq,rq);
    return p1+p2;
}
void update(node *root,int l,int r,int lq,int rq,int val){
    prop(root,l,r);
    if(l>=lq&&r<=rq){
        root->lzAdd+=val;
        prop(root,l,r);
        return ;
    }
    if(l>rq||r<lq)return ;
    int md = (l+r)/2;
    if(root->nxt[0]==NULL)root->nxt[0] = new node();
    if(root->nxt[1]==NULL)root->nxt[1] = new node();
    update(root->nxt[0],l,md,lq,rq,val);
    update(root->nxt[1],md+1,r,lq,rq,val);
    root->sum = root->nxt[0]->sum+root->nxt[1]->sum;
}

int main(){
    int t;
    cin>>t;
    long long d = 0;
    node* root = new node();
    while(t--){
        long long a,b,c;cin>>a>>b>>c;
        b+=d;c+=d;
        if(a==1){
            d = query(root,1,1e9,b,c);
            cout<<d<<endl;
        }else{
            update(root,1,1e9,b,c,1);
        }
    }
}

• Subtask 1: 100 / 100