oj.uz

Submission #954519

# Submission time Handle Problem Language Result Execution time Memory
954519 2024-03-28T05:45:13 Z hanifchdn Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 251 ms 153228 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[32 * 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 (tr < l or r < tl) return;
	if (l <= tl and tr <= r) {
		st[x].lazy = 1;
		push(x);
		return;
	}
	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) {
		update(st[x].l, l, r);
		update(st[x].r, l, 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 (tr < l or r < tl) return 0;
	if (l <= tl and tr <= r) return st[x].sum;
	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;
	}
	return get(st[x].l, l, r) + get(st[x].r, l, r);
}

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 14 ms 75356 KB Output is correct
2 Correct 13 ms 75608 KB Output is correct
3 Correct 13 ms 75436 KB Output is correct
4 Correct 22 ms 75624 KB Output is correct
5 Correct 23 ms 75612 KB Output is correct
6 Correct 23 ms 75608 KB Output is correct
7 Correct 24 ms 75608 KB Output is correct
8 Correct 90 ms 75608 KB Output is correct
9 Correct 187 ms 75856 KB Output is correct
10 Correct 186 ms 75944 KB Output is correct
11 Runtime error 251 ms 153228 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -