Submission #1181819

#TimeUsernameProblemLanguageResultExecution timeMemory
1181819AlishMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
0 ms320 KiB
#include<bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef long double     ld;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("input19.txt" , "r" , stdin) ;

const int INF=1e1;

struct Node{
    Node *lc, *rc;
    int sum=0;
    Node():lc(NULL), rc(NULL), sum(0){}
};

Node *root=new Node();

void upd(int lx, int rx, int l=1, int r=INF+1, Node *seg=root){
    if(lx>=r || rx<=l || seg->sum==r-l) return;
    if(lx<=l && rx>=r){
        seg->sum=r-l;
        return;
    }
    int mid=(r+l)>>1;
    if(!seg->lc) seg->lc=new Node();
    if(!seg->rc) seg->rc=new Node();
    upd(lx, rx, l, mid, seg->lc); upd(lx, rx, mid, r, seg->rc);
    seg->sum=seg->lc->sum+seg->rc->sum;
}

int get(int lx, int rx, int l=1, int r=INF+1, Node *seg=root){
    if(lx>=r || rx<=l || !seg->sum) return 0;
    if(lx<=l && rx>=r)return seg->sum;
    int mid=(r+l)>>1;
    if(seg->sum==r-l)return min(rx, r)-max(lx, l);
    return get(lx, rx, l, mid, seg->lc)+get(lx, rx, mid, r, seg->rc);
}

int main()
{
    fast_io
    int c=0;
    int q; cin>>q;
    while(q--){
        int t; cin>>t;
        if(t==1){
            int l, r; cin>>l>>r;
            l+=c; r+=c;
            c=get(l, r+1);
            cout<<c<<endl;
        }
        else{
            int l, r; cin>>l>>r;
            l+=c; r+=c;
            upd(l, r+1);
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...