oj.uz

답안 #538285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
538285 2022-03-16T13:33:52 Z fcw 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 495 ms 133316 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;


struct node{
	int sum, lz, l, r;
	node(): sum(0), lz(0), l(0), r(0) {}
};

vector<node>seg;

int create(){
	seg.push_back(node());
	return seg.size() - 1;
}

void push(int v, int l, int r){
	if(seg[v].lz){
		seg[v].sum = (r - l + 1) * seg[v].lz;
		if(!seg[v].l) seg[v].l = create();
		if(!seg[v].r) seg[v].r = create();
		seg[seg[v].l].lz = seg[seg[v].r].lz = 1;
		seg[v].lz = 0;
	}
}


void update(int v, int l, int r, int a, int b, int val){
	if(b < l || r < a) return;
	push(v, l, r);
	if(a <= l && r <= b){
		seg[v].lz = 1;
		push(v, l, r);
		return;
	}
	int m = (l + r) >> 1;
	if(!seg[v].l) seg[v].l = create();
	if(!seg[v].r) seg[v].r = create();
	update(seg[v].l, l, m, a, b, val);
	update(seg[v].r, m+1, r, a, b, val);
	push(seg[v].l, l, m);
	push(seg[v].r, m+1, r);
	seg[v].sum = seg[seg[v].l].sum + seg[seg[v].r].sum;
}

int query(int v, int l, int r, int a, int b){
	if(b < l || r < a) return 0;
	if(v == 0) return 0;
	push(v, l, r);
	if(a <= l && r <= b){
		return seg[v].sum;
	}
	int m = (l + r) >> 1;
	return query(seg[v].l, l, m, a, b) + query(seg[v].r, m+1, r, a, b);
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	create();
	create();
	int q;
	cin>>q;
	int c = 0;
	for(int i=0;i<q;i++){
		int op, x, y;
		cin>>op>>x>>y;
		if(op == 2) update(1, 1, int(1e9 + 7), x + c, y + c, 1);
		else{
			int cnt = query(1, 1, int(1e9 + 7), x + c, y + c);
			cout<<cnt<<"\n";
			c = cnt;
		}
	}


	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 17 ms 4672 KB Output is correct
5 Correct 19 ms 4676 KB Output is correct
6 Correct 19 ms 4640 KB Output is correct
7 Correct 20 ms 4684 KB Output is correct
8 Correct 144 ms 33936 KB Output is correct
9 Correct 301 ms 67680 KB Output is correct
10 Correct 341 ms 67572 KB Output is correct
11 Correct 342 ms 67428 KB Output is correct
12 Correct 319 ms 67332 KB Output is correct
13 Correct 305 ms 67388 KB Output is correct
14 Correct 305 ms 67396 KB Output is correct
15 Correct 435 ms 133204 KB Output is correct
16 Correct 495 ms 133316 KB Output is correct
17 Correct 296 ms 68644 KB Output is correct
18 Correct 323 ms 68492 KB Output is correct
19 Correct 440 ms 133272 KB Output is correct
20 Correct 461 ms 133168 KB Output is correct