Submission #1365981

#TimeUsernameProblemLanguageResultExecution timeMemory
1365981ttparin_Monkey and Apple-trees (IZhO12_apple)C++20
0 / 100
0 ms344 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
 int dp=0;
 int lz=0;
 node *left=nullptr;
 node *right=nullptr;
};
//node *root=new node;
void update(node *cur,int l,int r,int x,int y){
 if(x>r||y<l)
    return;
 if(cur->lz==1)
    cur->dp=(r-l+1);
 if(l==r){
    cur->lz=0;
    if(x<=l&&y>=l)
        cur->dp=1;
    return;
 }
 if(cur->right==nullptr)
 cur->right=new node;
 if(cur->left==nullptr)
    cur->left=new node;
 cur->left->lz=max(cur->left->lz,cur->lz);
 cur->right->lz=max(cur->right->lz,cur->lz);
 cur->lz=0;
 int mid=(l+r)/2;
 if(x<=l&&y>=r){
    cur->dp=(r-l+1);
    cur->left->lz=1;
    cur->right->lz=1;
    return;
 }
 /*if(x>r||y<l)
    return;*/
 update(cur->left,l,mid,x,y);
 update(cur->right,mid+1,r,x,y);
 int g=cur->left->dp;
 int j=cur->right->dp;
 if(cur->left->lz==1)
    g=mid-l+1;
 if(cur->right->lz==1)
    j=r-mid;
 cur->dp=g+j;
 return;
}
int read(node *cur,int l,int r,int x,int y){
 if(x>r||y<l)
    return 0;
 if(cur->lz==1)
    cur->dp=(r-l+1);
 if(l!=r){
    if(cur->right==nullptr)
 cur->right=new node;
 if(cur->left==nullptr)
    cur->left=new node;
 cur->left->lz=max(cur->left->lz,cur->lz);
 cur->right->lz=max(cur->right->lz,cur->lz);
 }
 cur->lz=0;
 /*if(x>r||y<l)
    return 0;*/
 if(x<=l&&y>=r)
    return(cur->dp);
 int mid=(l+r)/2;
 return(read(cur->left,l,mid,x,y)+read(cur->right,mid+1,r,x,y));
}
signed main(){
 ios_base::sync_with_stdio(0);cin.tie(0);
 node *root=new node;
 int n;
 cin>>n;
 int type,x,y;
 int ans=0;
 for(int i=1;i<=n;i++){
    cin>>type;
    if(type==2){
        cin>>x>>y;
        update(root,1,1e9,x+ans,y+ans);
    }
    else{
        cin>>x>>y;
        int ansss=read(root,1,1e9,x+ans,y+ans);
        cout<<ansss<<"\n";
        ans+=ansss;
    }
 }
 return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...