oj.uz

답안 #887880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887880 2023-12-15T12:13:19 Z NintsiChkhaidze 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 402 ms 208040 KB 
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define pii pair<int,int>
#define left t->l,l,(l + r)/2
#define right t->r,(l + r)/2 + 1,r
using namespace std;

const int inf = 1000000000;

struct Node {
    ll s,lz;
    Node *l, *r;
    Node() : s(0), lz(0), l(NULL), r(NULL) { }
};

void children(Node *t){
	if (!(t->l)) t->l = new Node();
	if (!(t->r)) t->r = new Node();
}
void push(Node *t,int l,int r){
	if ((t -> lz) == 0) return;

	int k = t -> lz;
	(t -> l) -> lz = k;
	(t -> l) -> s = (l + r)/2 - l + 1;
	
	(t -> r) -> lz = k;
	(t -> r) -> s = r - (l + r)/2;

	(t -> lz) = 0;
}

void upd(Node *t,int l,int r,int L,int R){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		t -> s = (r - l + 1);
		t -> lz = 1;
		return;
	}

	if (!t->l) t->l = new Node();
	if (!t->r) t->r = new Node();

	children(t);
	push(t,l,r);
	upd(left,L,R);
	upd(right,L,R);
	t->s = (t->l)->s + (t->r)->s;
}

int get(Node *t,int l,int r,int L,int R){
	if (t==NULL || r < L || R < l) return 0;
	if (L <= l && r <= R) return t->s;

	children(t);
	push(t,l,r);
	return get(left,L,R) + get(right,L,R);
}

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int q,c = 0;
	cin>>q;

	Node *root = new Node();

	while (q--){
		int tp,l,r;
		cin>>tp>>l>>r;
		l += c;
		r += c;

		if (tp == 1){
			c = get(root,1,inf,l,r);
			cout<<c<<endl;
		}else{
			upd(root,1,inf,l,r);
		}
	}
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 17 ms 4964 KB Output is correct
5 Correct 18 ms 5980 KB Output is correct
6 Correct 17 ms 5980 KB Output is correct
7 Correct 18 ms 5988 KB Output is correct
8 Correct 122 ms 44728 KB Output is correct
9 Correct 251 ms 77396 KB Output is correct
10 Correct 263 ms 85564 KB Output is correct
11 Correct 268 ms 91728 KB Output is correct
12 Correct 283 ms 94676 KB Output is correct
13 Correct 256 ms 109908 KB Output is correct
14 Correct 261 ms 111200 KB Output is correct
15 Correct 402 ms 201916 KB Output is correct
16 Correct 381 ms 203344 KB Output is correct
17 Correct 262 ms 114772 KB Output is correct
18 Correct 257 ms 114944 KB Output is correct
19 Correct 377 ms 207696 KB Output is correct
20 Correct 383 ms 208040 KB Output is correct