oj.uz

답안 #954514

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954514 2024-03-28T05:43:42 Z hanifchdn 원숭이와 사과 나무 (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) {
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 151056 KB Output is correct
2 Correct 42 ms 150612 KB Output is correct
3 Correct 43 ms 150608 KB Output is correct
4 Correct 54 ms 150612 KB Output is correct
5 Correct 85 ms 150616 KB Output is correct
6 Correct 56 ms 150600 KB Output is correct
7 Correct 56 ms 150708 KB Output is correct
8 Correct 164 ms 150836 KB Output is correct
9 Correct 263 ms 151076 KB Output is correct
10 Correct 254 ms 151124 KB Output is correct
11 Correct 242 ms 151124 KB Output is correct
12 Correct 266 ms 151120 KB Output is correct
13 Correct 204 ms 151124 KB Output is correct
14 Correct 231 ms 151260 KB Output is correct
15 Execution timed out 2659 ms 262144 KB Time limit exceeded
16 Halted 0 ms 0 KB -