Submission #655157

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
655157	2022-11-03T12:09:35 Z	pragmatist	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	433 ms	198176 KB

apple

/*#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/

#include<bits/stdc++.h>
 
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"

using namespace std;
using pii = pair<int, int>;

const int N = (int)1e5 + 7; // make sure this is right
const int M = (int)15e6 + 7;
const int inf = (int)1e9 + 7;
const ll INF = (ll)3e18 + 7;
const ll MOD = (ll)998244353; // make sure this is right

pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int L[M], R[M], add[M], timer;

ll t[M];

void push(int v, int tl, int tr) {
	if(add[v] == -1) return;
	if(tl != tr) {
		if(L[v]) {
			add[L[v]] = add[v];
		}
		if(R[v]) {
			add[R[v]] = add[v];
		}
	}        
	t[v] = 1ll * (tr - tl + 1) * add[v];
	add[v] = -1;
}

void upd(int v, int tl, int tr, int l, int r) {
	if(!L[v]) L[v] = ++timer;
	if(!R[v]) R[v] = ++timer;
	push(v, tl, tr);
	if(tl >= l && tr <= r) {
		add[v] = 1;
		push(v, tl, tr);
		return;	
	}
	if(tl > r || l > tr)
		return;
	int mid = (tl + tr) >> 1;
	upd(L[v], tl, mid, l, r);
	upd(R[v], mid + 1, tr, l, r);
	t[v] = t[L[v]] + t[R[v]];
}

ll get(int v, int tl, int tr, int l, int r) {
	if(!L[v]) L[v] = ++timer;
	if(!R[v]) R[v] = ++timer;
	push(v, tl, tr);
	if(tl >= l && tr <= r)
		return t[v];
	if(tl > r || l > tr || !v)
		return 0;
	int mid = (tl + tr) / 2;
	return get(L[v], tl, mid, l, r) + get(R[v], mid + 1, tr, l, r);
}

void solve() {
	fill(add, add + M, -1);
	int q; 
	cin >> q;
	timer = 1;
	int o = 1e9, C = 0;
	while(q--) {
		int tp;
		ll l, r, x;
		cin >> tp;
		if(tp == 2) {
			cin >> l >> r;                      
			upd(1, 1, o, l + C, r + C);		
		} else {
			cin >> l >> r;
			cout << (C = get(1, 1, o, l + C, r + C)) << "\n";		
		}
	}
}                                                                                       	

signed main() {	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int test = 1;
	//cin >> test;
	for(int i = 1; i <= test; ++i) {
	 	//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

Compilation message

apple.cpp: In function 'void solve()':
apple.cpp:13:11: warning: unused variable 'first' [-Wunused-variable]
   13 | #define x first
      |           ^~~~~
apple.cpp:85:12: note: in expansion of macro 'x'
   85 |   ll l, r, x;
      |            ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	59124 KB	Output is correct
2	Correct	27 ms	59040 KB	Output is correct
3	Correct	26 ms	59004 KB	Output is correct
4	Correct	35 ms	62104 KB	Output is correct
5	Correct	38 ms	62892 KB	Output is correct
6	Correct	38 ms	62668 KB	Output is correct
7	Correct	45 ms	62900 KB	Output is correct
8	Correct	134 ms	88856 KB	Output is correct
9	Correct	294 ms	111184 KB	Output is correct
10	Correct	271 ms	116436 KB	Output is correct
11	Correct	277 ms	120652 KB	Output is correct
12	Correct	309 ms	122564 KB	Output is correct
13	Correct	260 ms	132940 KB	Output is correct
14	Correct	258 ms	133656 KB	Output is correct
15	Correct	410 ms	194172 KB	Output is correct
16	Correct	433 ms	195188 KB	Output is correct
17	Correct	254 ms	136160 KB	Output is correct
18	Correct	259 ms	136260 KB	Output is correct
19	Correct	428 ms	198168 KB	Output is correct
20	Correct	379 ms	198176 KB	Output is correct