Submission #947450

#	Time	Username	Problem	Language	Result	Execution time	Memory
947450		oblantis	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	33 ms	3084 KiB

apple

//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e7 + 12;
int c, cnt, xl, xr;
struct node{
	int l, r, s;
} t[maxn];
void init(){
	t[cnt].l = t[cnt].r = -1;
	t[cnt].s = 0;
	cnt++;
}
void get(node& v, int lx, int rx){
	if(xr < lx || rx < xl)return;
	if(v.s == rx - lx + 1){
		c += min(xr, rx) - max(lx, xl) + 1;
		return;
	}
	if(v.s == 0)return;
	get(t[v.l], lx, (lx + rx) / 2), get(t[v.r], (lx + rx) / 2 + 1, rx);
}
void upd(node& v, int lx, int rx){
	if(xr < lx || rx < xl)return;
	if(v.s == rx - lx + 1){
		return;
	}
	if(xl <= lx && rx <= xr){
		v.s = rx - lx + 1;
		return;
	}
	if(v.l == -1){
		v.l = cnt;
		init();
	}
	if(v.r == -1){
		v.r = cnt;
		init();
	}
	upd(t[v.l], lx, (lx + rx) / 2), upd(t[v.r], (lx + rx) / 2 + 1, rx);	
	v.s = t[v.l].s + t[v.r].s;
}
void solve() {
	int m;
	cin >> m;
	init();
	for(int i = 0; i < m; i++){
		int wt;
		cin >> wt >> xl >> xr;
		xl = xl + c, xr = xr + c;
		if(wt == 1){
			c = 0;
			get(t[0], 1, inf);
			cout << c << '\n';
		}
		else {
			upd(t[0], 1, inf);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

• Subtask 1: 100 / 100