oj.uz

Submission #954970

# Submission time Handle Problem Language Result Execution time Memory
954970 2024-03-29T03:16:56 Z hanifchdn Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 299 ms 262144 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, tl, tr, l, r;
	node() : sum(0), lazy(0), l(-1), r(-1) {}
};

node st[64 * N];
int cnt = 1;

void push(int x) {
	if (!st[x].lazy) return;
	int tl = st[x].tl, tr = st[x].tr, tm = (tl + tr) / 2;
	st[x].sum = st[x].tr - st[x].tl + 1;
	if (st[x].l == -1 and tl != tr) {
		st[x].l = ++cnt;
		st[cnt].tl = tl;
		st[cnt].tr = tm;
		st[x].r = ++cnt;
		st[cnt].tl = tm + 1;
		st[cnt].tr = tr;
	}
	if (tl != tr) {
		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 l, int r) {
	push(x);
	int tl = st[x].tl, tr = st[x].tr, tm = (tl + tr) / 2;
	if (l <= tl and tr <= r) {
		st[x].lazy = 1;
		push(x);
		return;
	}
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[cnt].tl = tl;
		st[cnt].tr = tm;
		st[x].r = ++cnt;
		st[cnt].tl = tm + 1;
		st[cnt].tr = tr;
	}
	if (r > tm) {
		update(st[x].r, l, r);
		push(st[x].l);
	}
	if (l <= tm) {
		update(st[x].l, l, r);
		push(st[x].r);
	}
	st[x].sum = st[st[x].l].sum + st[st[x].r].sum;
}

int get(int x, int l, int r) {
	push(x);
	int tl = st[x].tl, tr = st[x].tr, 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[cnt].tl = tl;
		st[cnt].tr = tm;
		st[x].r = ++cnt;
		st[cnt].tl = tm + 1;
		st[cnt].tr = tr;
	}
	if (r > tm) res += get(st[x].r, l, r);
	if (l <= tm) res += get(st[x].l, l, r);
	return res;
}

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    st[1].sum = 0;
    st[1].lazy = 0;
    st[1].tl = 1;
    st[1].tr = 1e9;
    int q;
    cin >> q;
    int c = 0;
    while (q--) {
    	int d, x, y;
    	cin >> d >> x >> y;
    	if (d == 1) {
    		c = get(1, x + c, y + c);
    		cout << c << "\n";
    	}
    	else {
    		update(1, x + c, y + c);
    	}
    }	
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 150612 KB Output is correct
2 Correct 43 ms 150612 KB Output is correct
3 Correct 44 ms 150608 KB Output is correct
4 Correct 49 ms 150620 KB Output is correct
5 Correct 51 ms 150612 KB Output is correct
6 Correct 51 ms 150616 KB Output is correct
7 Correct 49 ms 150764 KB Output is correct
8 Correct 121 ms 150988 KB Output is correct
9 Correct 203 ms 151124 KB Output is correct
10 Correct 212 ms 151028 KB Output is correct
11 Correct 218 ms 151112 KB Output is correct
12 Correct 247 ms 151072 KB Output is correct
13 Correct 190 ms 151124 KB Output is correct
14 Correct 215 ms 151292 KB Output is correct
15 Runtime error 299 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -