Submission #867869

# Submission time Handle Problem Language Result Execution time Memory
867869 2023-10-29T16:16:09 Z vjudge1 Monkey and Apple-trees (IZhO12_apple) C++11
0 / 100
1 ms 2396 KB
#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;
		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);
		}
	}
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -