Submission #1301906

#TimeUsernameProblemLanguageResultExecution timeMemory
1301906muhammad-mutahirMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
472 ms251232 KiB
#include <bits/stdc++.h>
using namespace std;

#define print(l) for(auto i:l) cout<<i<<" ";cout<<endl;
#define input(t,l,n) vector<t>l(n);for(int i = 0;i<n;i++)cin>>l[i];
// #define int long long
#define pb push_back
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define all(l) l.begin(),l.end()
#define pii pair<int,int>
#define fi first
#define se second

const int M = 1e9+7;
const int inf = 1e18;


int bp(int x, int y, int p){
    int res = 1;
    x = x % p;
    while (y > 0) {
 
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
int MI(int n, int p){
    return bp(n, p - 2, p);
}
int mul(int x,int y, int p){
    return x * 1ull * y % p;
}
int di(int x,int y, int p){
    return mul(x, MI(y, p), p);
}

struct Node{
	int val;
	int mi;
	int cnt;
	int lz;
	Node *L,*R;
};

Node* getnode(){
	Node* tp = new Node;
	tp->lz = 0;
	tp->val = 0;
	tp->mi = 0;
	tp->cnt = 0 ; 
	tp->L = NULL;
	tp->R = NULL;
	return tp;
}

Node* root = getnode();


void lazy(Node* curr,int s,int e){
	if(curr->lz ==0){
		return;
	}
	int m = (s+e)/2;
	if(curr->L == NULL){
		curr->L = getnode();
		curr->L->cnt = m-s; 
	}
	if(curr->R == NULL){
		curr->R = getnode();
		curr->R->cnt = e-m;
	}
	
	curr->L->lz += curr->lz;
	curr->L->val += curr->lz*(m-s) ;
	curr->L->mi+=curr->lz;
	
	curr->R->lz += curr->lz;
	curr->R->val += curr->lz*(e-m);
	curr->R->mi+=curr->lz;
		
	curr->lz = 0;
	
		// cout<<cur->val<<" "<<s<<" "<<e<<endl;
}
void Update(Node* cur,long long l,long long r,int c,long long s = 0 ,long long e = (1ll<<31)){

	if(l<=s and e<=r){
		cur->val+= c*(e-s);
		cur->lz += c;
		cur->mi += c;
		cur->cnt = e-s;
		// cout<<"F ff "<<s<<" "<<e<<" "<<cur->mi<<" "<< cur->cnt <<endl;
		return;
	}
	if(e<=l or r<=s){
		return;
	}
	lazy(cur,s,e);
	long long m = (s+e)/2;
	if(!(m<=l or r<=s)){
		if(cur->L == NULL){
			cur->L = getnode();
			cur->L->cnt = m-s; 
		}
		Update(cur->L,l,r,c,s,m);
		cur->val += cur->L->val;
	}
	if(!(e<=l or r<=m)){
		if(cur->R == NULL){
			cur->R = getnode();
			cur->R->cnt = e-m; 
		}
		Update(cur->R,l,r,c,m,e);
		
		cur->val += cur->R->val;
	}

	int x = inf;
	
	if(cur->L != NULL){
		x = cur->L->mi;
	}
	else{
		x = 0 ;
	}
	if(cur->R != NULL){
		x = min(cur->R->mi,x);
	}
	else{
		x = 0;
	}
	
	cur->mi = x;
	
	cur->cnt = 0;
	
	if(cur->L != NULL and cur->L->mi == cur->mi){
		cur->cnt += cur->L->cnt;
	}
	else if(cur->L == NULL){
		cur->cnt+=m-s;
	}
	if(cur->R != NULL and cur->R->mi == cur->mi){
		cur->cnt += cur->R->cnt;
	}
	else if(cur->R == NULL){
		cur->cnt += e-m;
	}
	// if(s == 0 and e == 8){
		// cout<<cur->mi<<" "<<cur->cnt<<endl;
		// cout<<cur->L->mi<<" "<<cur->L->cnt<<" "<<cur->R->mi<<" "<<cur->R->cnt<<endl;
	// }	
}
pair<int,int> fans;

void get(Node* cur,long long l,long long r,long long s = 0, long long e = (1ll<<31)){

	
	lazy(cur,s,e);
	if(l<=s and e<=r){
		if(fans.fi == cur->mi){
			fans.se += cur->cnt;
		}
		else if(fans.fi > cur->mi ){
			fans.fi = cur->mi;
			fans.se = cur->cnt;
		}
		return;
		// cout<<s<<" "<<e<<" "<<l<<" "<<r<<endl;
		// ans+=cur->val;
		// return {cur->mi,cur->cnt};
	}
	if(e<=l or r<=s){
		// return {inf,0};
		return;
	}

	pair<int,int>ans,ans1;
	// ans = {inf,0};
	// ans1 = {inf,0};
	
	long long  m = (s+e)/2;
	// cout<<s<<" "<<m<<" "<<m<<" "<<e<<endl;
	if(!(m<=l or r<=s)){
		if(cur->L == NULL){
			cur->L = getnode();
			cur->L->cnt = m-s;
		}
		get(cur->L,l,r,s,m);
		
	}
	if(!(e<=l or r<=m)){
		if(cur->R == NULL){
			cur->R = getnode();
			cur->R->cnt = e-m;
		}
		get(cur->R,l,r,m,e);
	}
	return;
	// int mi = min(ans.fi,ans1.fi);
	// int cnt = 0;
	// cout<<ans.fi<<" "<<ans.se<<" "<<ans1.fi<<" "<<ans1.se<<endl;
	// if(ans.fi == mi){
		// cnt+=ans.se;
	// }
	// if(ans1.fi == mi){
		// cnt+=ans1.se;
	// }
	// return {mi,cnt};
	
}
// 
int n , m , k , q;

void solve(int testcase_number){
	root->cnt = (1ll<<31);

    cin>>n;
    int c =0 ;
    for(int i =0 ;i<n;i++){
    	int t;
    	cin>>t;
    		int l,r;
    		cin>>l>>r;
    		l--;

    		l+=c;
    		r+=c;
    	if(t == 1){
    		int val = r-l;
    		// pair<int,int> ans = get(root,l,r);
    		fans.fi = inf;
    		fans.se = 0;
    		get(root,l,r);
    		// cout<<l<<" "<<r<<" "<<ans.fi<<" "<<ans.se<<endl;
    		if(fans.fi == 0){
    			val-=fans.se;
    		}
    		cout<<val<<endl;
    		c = val;
    	}
    	else{
    		// cout<<endl;
    		Update(root,l,r,1);
    	}
    }




}


signed main(){
    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);
    cout << fixed<<setprecision(9);

    int t = 1;
    // cin>>t;
    for(int i = 1;i<=t;i++){
        solve(i);
    }

}

Compilation message (stderr)

apple.cpp:15:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const int inf = 1e18;
      |                 ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...