Submission #768269

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
768269	2023-06-27T20:44:10 Z	Ahmed57	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	616 ms	262144 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	21 ms	5904 KB	Output is correct
5	Correct	25 ms	7128 KB	Output is correct
6	Correct	25 ms	6860 KB	Output is correct
7	Correct	25 ms	7128 KB	Output is correct
8	Correct	184 ms	52300 KB	Output is correct
9	Correct	346 ms	89136 KB	Output is correct
10	Correct	357 ms	99784 KB	Output is correct
11	Correct	374 ms	108208 KB	Output is correct
12	Correct	371 ms	111912 KB	Output is correct
13	Correct	364 ms	138956 KB	Output is correct
14	Correct	390 ms	140308 KB	Output is correct
15	Correct	576 ms	254540 KB	Output is correct
16	Correct	616 ms	256512 KB	Output is correct
17	Correct	388 ms	145372 KB	Output is correct
18	Correct	407 ms	145408 KB	Output is correct
19	Correct	580 ms	262144 KB	Output is correct
20	Correct	579 ms	262144 KB	Output is correct