Submission #1092194

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1092194	2024-09-23T13:44:37 Z	Nurislam	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	400 ms	209580 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	16 ms	5072 KB	Output is correct
5	Correct	20 ms	6232 KB	Output is correct
6	Correct	20 ms	5972 KB	Output is correct
7	Correct	19 ms	5976 KB	Output is correct
8	Correct	133 ms	45136 KB	Output is correct
9	Correct	265 ms	77068 KB	Output is correct
10	Correct	292 ms	86608 KB	Output is correct
11	Correct	276 ms	93012 KB	Output is correct
12	Correct	290 ms	95824 KB	Output is correct
13	Correct	261 ms	111056 KB	Output is correct
14	Correct	269 ms	111960 KB	Output is correct
15	Correct	370 ms	203464 KB	Output is correct
16	Correct	367 ms	205136 KB	Output is correct
17	Correct	268 ms	115540 KB	Output is correct
18	Correct	261 ms	115796 KB	Output is correct
19	Correct	386 ms	209488 KB	Output is correct
20	Correct	400 ms	209580 KB	Output is correct