oj.uz

Submission #954974

# Submission time Handle Problem Language Result Execution time Memory
954974 2024-03-29T03:49:29 Z hanifchdn Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 300 ms 205856 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
 
const int N = 1e5 + 5;
 
struct node {
	int sum, lazy, l, r;
	node() : sum(0), lazy(0), l(-1), r(-1) {}
};
 
node st[64 * N];
int cnt = 1;
 
void push(int x, int tl, int tr) {
	if (!st[x].lazy) return;
	st[x].sum = tr - tl + 1;
	if (tl == tr) {
		st[x].lazy = 0;
		return;
	}
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[x].r = ++cnt;
	}
	st[st[x].l].lazy = st[x].lazy;
	st[st[x].r].lazy = st[x].lazy;
	st[x].lazy = 0;
}
 
void update(int x, int tl, int tr, int l, int r) {
	push(x, tl, tr);
	int tm = (tl + tr) / 2;
	if (tr < l or r < tl) return;
	if (l <= tl and tr <= r) {
		st[x].lazy = 1;
		push(x, tl, tr);
		return;
	}
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[x].r = ++cnt;
	}
	update(st[x].l, tl, tm, l, r);
	update(st[x].r, tm + 1, tr, l, r);
	st[x].sum = st[st[x].l].sum + st[st[x].r].sum;
}
 
int get(int x, int tl, int tr, int l, int r) {
	if (tr < l or r < tl) return 0;
	push(x, tl, tr);
	int tm = (tl + tr) / 2;
	if (l <= tl and tr <= r) return st[x].sum;
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[x].r = ++cnt;
	}
	return get(st[x].l, tl, tm, l, r) + get(st[x].r, tm + 1, tr, l, r);
}
 
int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int q;
    cin >> q;
    int c = 0;
    while (q--) {
    	int d, x, y;
    	cin >> d >> x >> y;
    	if (d == 1) {
    		c = get(1, 1, 1e9, x + c, y + c);
    		cout << c << "\n";
    	}
    	else {
    		update(1, 1, 1e9, x + c, y + c);
    	}
    }	
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 100432 KB Output is correct
2 Correct 23 ms 100448 KB Output is correct
3 Correct 21 ms 100440 KB Output is correct
4 Correct 29 ms 100700 KB Output is correct
5 Correct 33 ms 100604 KB Output is correct
6 Correct 33 ms 100648 KB Output is correct
7 Correct 34 ms 100692 KB Output is correct
8 Correct 82 ms 101348 KB Output is correct
9 Correct 174 ms 101976 KB Output is correct
10 Correct 157 ms 101972 KB Output is correct
11 Correct 161 ms 102040 KB Output is correct
12 Correct 177 ms 102132 KB Output is correct
13 Correct 154 ms 102160 KB Output is correct
14 Correct 151 ms 102164 KB Output is correct
15 Runtime error 300 ms 205856 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -