Submission #947450

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
947450	2024-03-16T08:09:39 Z	oblantis	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	33 ms	3084 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	496 KB	Output is correct
4	Correct	4 ms	592 KB	Output is correct
5	Correct	3 ms	604 KB	Output is correct
6	Correct	4 ms	604 KB	Output is correct
7	Correct	3 ms	600 KB	Output is correct
8	Correct	14 ms	1372 KB	Output is correct
9	Correct	29 ms	2392 KB	Output is correct
10	Correct	29 ms	2396 KB	Output is correct
11	Correct	31 ms	2524 KB	Output is correct
12	Correct	27 ms	2392 KB	Output is correct
13	Correct	32 ms	2900 KB	Output is correct
14	Correct	33 ms	2896 KB	Output is correct
15	Correct	27 ms	3080 KB	Output is correct
16	Correct	31 ms	2896 KB	Output is correct
17	Correct	25 ms	3084 KB	Output is correct
18	Correct	30 ms	2908 KB	Output is correct
19	Correct	27 ms	2908 KB	Output is correct
20	Correct	32 ms	2900 KB	Output is correct