oj.uz

Submission #954512

# Submission time Handle Problem Language Result Execution time Memory
954512 2024-03-28T05:41:06 Z hanifchdn Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 2000 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) {
	int tl = st[x].tl, tr = st[x].tr, tm = (tl + tr) / 2;
	st[x].sum = max(st[x].sum, (st[x].tr - st[x].tl + 1) * st[x].lazy);
	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;
	if (tr < l or r < tl) return;
	if (l <= tl and tr <= r) {
		st[x].lazy = 1;
		push(x);
		return;
	}
	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;
	if (tr < l or r < tl) return 0;
	if (l <= tl and tr <= r) return st[x].sum;
	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 71 ms 150612 KB Output is correct
2 Correct 41 ms 150612 KB Output is correct
3 Correct 40 ms 150620 KB Output is correct
4 Correct 48 ms 150864 KB Output is correct
5 Correct 52 ms 150868 KB Output is correct
6 Correct 51 ms 150848 KB Output is correct
7 Correct 50 ms 150868 KB Output is correct
8 Correct 114 ms 151636 KB Output is correct
9 Correct 254 ms 152848 KB Output is correct
10 Correct 228 ms 152656 KB Output is correct
11 Correct 235 ms 153048 KB Output is correct
12 Correct 224 ms 152768 KB Output is correct
13 Correct 203 ms 153168 KB Output is correct
14 Correct 231 ms 153132 KB Output is correct
15 Execution timed out 2554 ms 262144 KB Time limit exceeded
16 Halted 0 ms 0 KB -