oj.uz

Submission #954971

# Submission time Handle Problem Language Result Execution time Memory
954971 2024-03-29T03:37:52 Z hanifchdn Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 284 ms 204624 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 (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 (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;
	}
	if (r > tm) update(st[x].r, tm + 1, tr, l, r);
	if (l <= tm) update(st[x].l, tl, tm, l, r);
	push(st[x].l, tl, tm);
	push(st[x].r, tm + 1, tr);
	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) {
	push(x, tl, tr);
	int tm = (tl + tr) / 2;
	if (l <= tl and tr <= r) return st[x].sum;
	int res = 0;
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[x].r = ++cnt;
	}
	if (r > tm) res += get(st[x].r, tm + 1, tr, l, r);
	if (l <= tm) res += get(st[x].l, tl, tm, l, r);
	return res;
}

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 50 ms 100436 KB Output is correct
2 Correct 28 ms 100400 KB Output is correct
3 Correct 25 ms 100444 KB Output is correct
4 Correct 33 ms 100576 KB Output is correct
5 Correct 37 ms 100564 KB Output is correct
6 Correct 33 ms 100480 KB Output is correct
7 Correct 35 ms 100456 KB Output is correct
8 Correct 85 ms 100668 KB Output is correct
9 Correct 176 ms 100948 KB Output is correct
10 Correct 189 ms 101192 KB Output is correct
11 Correct 172 ms 100844 KB Output is correct
12 Correct 174 ms 100948 KB Output is correct
13 Correct 163 ms 100996 KB Output is correct
14 Correct 163 ms 100948 KB Output is correct
15 Runtime error 284 ms 204624 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -