oj.uz

Submission #937811

# Submission time Handle Problem Language Result Execution time Memory
937811 2024-03-04T14:03:58 Z PagodePaiva Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
 307 ms 202580 KB 
#include<bits/stdc++.h>
#define N 300010
#define int long long

using namespace std;

int tree[40*N], lazy[40*N], L[40*N], R[40*N];
int idx = 1;
int mx = 1e9;

void unlazy(int node, int l, int r){
	if(l == r or !lazy[node]) return;
	// cout << node << ' ' << l << ' ' << r << ' ' << lazy[node] << endl;
	int mid = (l+r)/2;
	if(!L[node]) L[node] = ++idx;
	if(!R[node]) R[node] = ++idx;
	lazy[L[node]] = lazy[R[node]] = lazy[node]; lazy[node] = 0;
	tree[L[node]] = (mid-l+1)*lazy[L[node]];
	tree[R[node]] = (r-mid)*lazy[R[node]];
	return;
}

void update(int node, int l, int r, int tl, int tr, int val){
	if(l > tr or tl > r) return;
	unlazy(node, tl, tr);
	if(l <= tl and tr <= r){
		tree[node] = val*(tr-tl+1);
		lazy[node] = val;
		return;
	}
	int mid = (tl+tr)/2;
	if(l <= mid){
		if(!L[node]) L[node] = ++idx;
		update(L[node], l, r, tl, mid, val);
	}
	if(mid < r){
		if(!R[node]) R[node] = ++idx;
		update(R[node], l, r, mid+1, tr, val);
	}
	tree[node] = tree[L[node]] + tree[R[node]];
}

int query(int node, int l, int r, int tl, int tr){
	if(l > tr or tl > r or !node) return 0;
	unlazy(node, tl, tr);
	if(l <= tl and tr <= r) return tree[node];
	int mid = (tl+tr)/2;
	return query(L[node], l, r, tl, mid) + query(R[node], l, r, mid+1, tr);
}

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int q;
	cin >> q;
	int c = 0;
	while(q--){
		int t, x, y;
		cin >> t >> x >> y;
		x += c;
		y += c;
		if(t == 1){
			c = query(1, x, y, 1, mx);
			cout << c << "\n";
		}
		else{
			update(1, x, y, 1, mx, 1);
		}
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 9 ms 5720 KB Output is correct
5 Correct 15 ms 8180 KB Output is correct
6 Correct 11 ms 8224 KB Output is correct
7 Correct 11 ms 8284 KB Output is correct
8 Correct 86 ms 44408 KB Output is correct
9 Correct 197 ms 73228 KB Output is correct
10 Correct 194 ms 81216 KB Output is correct
11 Correct 210 ms 88588 KB Output is correct
12 Correct 210 ms 89940 KB Output is correct
13 Correct 176 ms 109572 KB Output is correct
14 Correct 173 ms 112140 KB Output is correct
15 Correct 307 ms 196436 KB Output is correct
16 Correct 275 ms 197976 KB Output is correct
17 Correct 192 ms 114056 KB Output is correct
18 Correct 179 ms 114144 KB Output is correct
19 Correct 283 ms 202580 KB Output is correct
20 Correct 279 ms 202524 KB Output is correct