Submission #1092194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092194		Nurislam	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	400 ms	209580 KiB

apple

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;

using namespace std;

#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long


template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}

const int N = 1e5+50, inf = 1e18+200;
//int mod = 998244353;
int mod = 1000000007;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)

struct node{
	node *left;
	node *right;
	int l, r, v;
};

void upd(int tl, int tr, node* res){
	if(res->l > tr || res->r < tl)return;
	if(tl <= res->l && res->r <= tr){
		res->v = res->r-res->l+1;
		return;
	}
	if(!(res->left)){
		res->left = new node;
		res->left->l = res->l;
		res->left->r = (res->l + res->r)>>1;
		res->left->v = 0;
		res->left->left = nullptr;
		res->left->right = nullptr;
	}
	if(!(res->right)){
		res->right = new node;
		res->right->l = (res->l + res->r)/2+1;
		res->right->r = res->r;
		res->right->v = 0;
		res->right->left = nullptr;
		res->right->right = nullptr;
	}
	if(res->v == (res->r - res->l + 1)){
		res->left->v = res->v/2;
		res->right->v = res->v/2;
	}
	upd(tl, tr, res->left);
	upd(tl, tr, res->right);
	res->v = res->left->v + res->right->v;
}


int get(int tl, int tr, node* res){
	if(res->l > tr || res->r < tl)return 0 ;
	if(tl <= res->l && res->r <= tr){
		return res->v;
	}
	if(!(res->left)){
		res->left = new node;
		res->left->l = res->l;
		res->left->r = (res->l + res->r)>>1;
		res->left->v = 0;
		res->left->left = nullptr;
		res->left->right = nullptr;
	}
	if(!(res->right)){
		res->right = new node;
		res->right->l = (res->l + res->r)/2+1;
		res->right->r = res->r;
		res->right->v = 0;
		res->right->left = nullptr;
		res->right->right = nullptr;
	}
	if(res->v == (res->r - res->l + 1)){
		res->left->v = res->v/2;
		res->right->v = res->v/2;
	}
	int ans = get(tl, tr, res->left);
	ans += get(tl, tr, res->right);
	return ans;
}

void solve(){
	node *d = new node;
	d->l = 0;
	d->r = INT_MAX>>1;
	d->v = 0;
	d->left = nullptr;
	d->right = nullptr;
	int q;
	cin >> q;
	int c = 0;
	while(q--){
		int t, l, r;
		cin >> t >> l >> r;
		if(t == 1){
			c = get(l+c, r+c, d);
			cout << c << endl;
		}else{
			upd(l+c, r+c, d);
		}
	}
}

 
signed main(){
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr);
	//cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
}
 
 
 
 
 
 
 
 
 
 
 
 
 

• Subtask 1: 100 / 100