Submission #867871

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
867871	2023-10-29T16:19:08 Z	vjudge1	Monkey and Apple-trees (IZhO12_apple)	C++11	0 / 100	1 ms	2396 KB

apple

#include <bits/stdc++.h>


using namespace std;

#define int long long

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

using ll = long long;
using ld = long double;
 
void solve(int T);
void pre();
 
const int N = 2e5 + 5;
const int M = 80 * N;
const int SQRT = 500;
const int LOG = 20;
const int INF = 1e18;
const int MOD = 1e9+7;
const ld EPS = 1e-9;

void pre(){
	#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
	#endif
	
}

int32_t main(){
	pre();
	int tt = 1;
	//cin>>tt;
	for(int i = 1;i<=tt;i++){
		//cerr<<"Case "<<i<<": "<<endl;
		solve(i);
	}
    return 0;
}

int id = 2;

int next(){
	return id++;
}

int L[M];
int R[M];
int A[M];

void push(int k,int l,int r){
	

	if(A[k] == r - l + 1){
		if(l != r){
			int m = (l + r)/2;

			A[L[k]] = m - l + 1;
			A[R[k]] = r - m;
			
		}
	}
}

void assign(int k,int l,int r){
	if(!L[k] && l != r){
		L[k] = next();
		R[k] = next();
	}
}

void update(int k,int l,int r,int x,int y){
	push(k, l , r);
	assign(k, l, r);
	if(r < x || y < l)return;

	if(x <= l && r <= y){
		A[k] = r - l + 1;
		push(k,l,r);
		return;
	}

	int m = (l + r)/2;
	update(L[k], l, m, x, y);
	update(R[k], m+1, r, x, y);
	A[k] = A[L[k]] + A[R[k]];
}

int query(int k,int l,int r,int x,int y){
	push(k, l , r);
	assign(k, l, r);
	if(r < x || y < l)return 0;
	if(x <= l && r <= y)return A[k];
	int m = (l + r) / 2;

	return query(L[k], l, m, x, y) + query(R[k], m+1, r, x, y);


}

void solve(int T){
	int q;
	cin>>q;
	int c = 0;
	while(q--){
		int t,x,y;
		cin>>t>>x>>y;

		if(t == 1){
			c = query(1,1,1e9,x+c,y+c);
			//cerr<<"kur"<<endl;
			cout<<c<<endl;
		}else{
			update(1, 1,1e9,x+c,y+c);
		}
	}
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Incorrect	1 ms	2396 KB	Output isn't correct
3	Halted	0 ms	0 KB	-