Submission #1000898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000898		0pt1mus23	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	217 ms	100692 KiB

apple

#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
// #define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; goto bitir;
#define all(x) x.begin(),x.end()
const int   mod = 1e9 +7,
            sze = 8*1e6 +10;
            // inf = 2e18,
            // prime = 4567896467;


int L[sze];
int R[sze];
int nxt =1;
int T[sze];
int Laz[sze];
void push(int node,int l,int r){
    // cout<<l<<" -> "<<r<<" pushlayiram"<<endl;
    if(Laz[node]){
        // cout<<l<<":"<<r<<" node:"<< node<<endl;
        T[node]= r-l+1;
        // cout<<"val "<<T[node]<<endl;

        if(l!=r){
            if(!L[node]){
                L[node]=++nxt;
            }
            Laz[L[node]]+=Laz[node];
            if(!R[node]){
                R[node]=++nxt;
            }
            Laz[R[node]]+=Laz[node]; 
        }
        Laz[node]=0;
        return;
    }
}
int qry(int node,int l,int r,int lx,int rx){
    if(lx>r || rx<l){
        return 0;
    }
    push(node,lx,rx);
    if(lx>=l && rx<=r){
        // cout<<node<<" goturdum"<<endl;
        // cout<<lx<<" "<<rx<<" sum:"<<T[node]<<endl;
        // cout<<lx<<":"<<rx<<" :-> "<<T[node]<<endl;
        return T[node];
    }
    int left =0 ;
    int right=0;
    int mid = (lx+rx)/2;
    if(L[node]){
        left = qry(L[node],l,r,lx,mid);
    }
    if(R[node]){
        right = qry(R[node],l,r,mid+1,rx);
    }

    return left+right;
}
int x=0;
void upd(int node,int l,int r,int lx,int rx){
    // cout<<node<<" "<<"sa"<<endl;
    if(lx>r || rx<l){
        return;
    }
    // cout<<l<<" "<<r<<" "<<lx<<" "<<rx<<endl;
    push(node,lx,rx);
    if(lx>=l && rx<=r){
        // cout<<lx<<" updateleniyor "<<rx<<endl;
        // cout<<x<<endl;
        Laz[node]++;
        push(node,lx,rx);
        // cout<<node<<endl;
        // cout<<lx<<" "<<rx<<" -------"<<T[node]<<endl;
        return;
    }
    int mid = (lx+rx)/2;
    if(!L[node]){
        L[node]=++nxt;    
    }
    upd(L[node],l,r,lx,mid);
    
    if(!R[node]){
        R[node]=++nxt;
    }
    upd(R[node],l,r,mid+1,rx);

    T[node]= max(T[node],T[L[node]] + T[R[node]]);
    // cout<<node<<" : "<<T[node]<<" "<<lx<<":"<<rx<<endl;
    // cout<<node<<" : "<<T[L[node]]<<", "<<T[R[node]]<<endl;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;
    
    while(tt--){
        int n = 1e9 +7;
        // upd(1,1,4,1,n);
        // upd(1,4,5,1,n);
        // // cout<<T[1]<<endl;
        // cout<<qry(1,1,10,1,n)<<endl;
        int q;
        cin>>q;
        int c =0;   
        while(q--){
            int d;
            cin>>d;
            x++;
            if(d==1){
                int l,r;
                cin>>l>>r;
                l+=c;
                r+=c;
                int res = qry(1,l,r,1,n);
                c=res;
                c=res;
                cout<<res<<endl;
            }
            else{
                int l,r;
                cin>>l>>r;
                l+=c;
                r+=c;
                upd(1,l,r,1,n);
            }
        }

        bitir:;
    }
}

Compilation message (stderr)

apple.cpp: In function 'int main()':
apple.cpp:136:9: warning: label 'bitir' defined but not used [-Wunused-label]
  136 |         bitir:;
      |         ^~~~~

• Subtask 1: 100 / 100