Submission #1000898

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1000898	2024-06-18T11:00:40 Z	0pt1mus23	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	217 ms	100692 KB

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

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	8 ms	5804 KB	Output is correct
5	Correct	9 ms	3160 KB	Output is correct
6	Correct	8 ms	2904 KB	Output is correct
7	Correct	9 ms	2908 KB	Output is correct
8	Correct	64 ms	21844 KB	Output is correct
9	Correct	135 ms	35664 KB	Output is correct
10	Correct	167 ms	39760 KB	Output is correct
11	Correct	152 ms	42836 KB	Output is correct
12	Correct	152 ms	44372 KB	Output is correct
13	Correct	127 ms	53332 KB	Output is correct
14	Correct	139 ms	53748 KB	Output is correct
15	Correct	217 ms	97876 KB	Output is correct
16	Correct	195 ms	98384 KB	Output is correct
17	Correct	126 ms	55680 KB	Output is correct
18	Correct	142 ms	55628 KB	Output is correct
19	Correct	190 ms	100608 KB	Output is correct
20	Correct	179 ms	100692 KB	Output is correct