답안 #950313

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950313 2024-03-20T08:00:46 Z nguyennh 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
304 ms 186704 KB
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define el '\n'
using namespace std ;
 
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

struct Node {
	int sum, lazy, tl, tr, l, r;
	Node() : sum(0), lazy(0), l(-1), r(-1) {}
};
 
const int MAXN = 123456;
Node segtree[64 * MAXN];
int cnt = 2;
 
void push_lazy(int node) {
	if (segtree[node].lazy) {
		segtree[node].sum = segtree[node].tr - segtree[node].tl + 1;
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
		segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1;
		segtree[node].lazy = 0;
	}
}
 
void update(int node, int l, int r) {
	push_lazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr) {
		segtree[node].lazy = 1;
		push_lazy(node);
	} else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
 
		if (l > mid) update(segtree[node].r, l, r);
		else if (r <= mid) update(segtree[node].l, l, r);
		else {
			update(segtree[node].l, l, mid);
			update(segtree[node].r, mid + 1, r);
		}
 
		push_lazy(segtree[node].l);
		push_lazy(segtree[node].r);
		segtree[node].sum =
		    segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
	}
}
 
int query(int node, int l, int r) {
	push_lazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr)
		return segtree[node].sum;
	else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
 
		if (l > mid) return query(segtree[node].r, l, r);
		else if (r <= mid) return query(segtree[node].l, l, r);
		else
			return query(segtree[node].l, l, mid) +
			       query(segtree[node].r, mid + 1, r);
	}
}
 
int32_t main (){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int m;
  cin >> m;
  int last = 0;
  segtree[1].tl = 1;
  segtree[1].tr = (int)1e9;
  for ( int i = 1 ; i <= m ; i++ ){
    int type , l , r;
    cin >> type >> l >> r;
    l += last;
    r += last;
    if (type == 1){
      last = query(1 , l , r);
      cout << last << el;
    }
    else update(1 , l , r);
  }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 185940 KB Output is correct
2 Correct 39 ms 185740 KB Output is correct
3 Correct 40 ms 185740 KB Output is correct
4 Correct 48 ms 185940 KB Output is correct
5 Correct 57 ms 185904 KB Output is correct
6 Correct 49 ms 185936 KB Output is correct
7 Correct 50 ms 185940 KB Output is correct
8 Correct 116 ms 186092 KB Output is correct
9 Correct 208 ms 186368 KB Output is correct
10 Correct 230 ms 186192 KB Output is correct
11 Correct 216 ms 186336 KB Output is correct
12 Correct 229 ms 186244 KB Output is correct
13 Correct 187 ms 186452 KB Output is correct
14 Correct 191 ms 186360 KB Output is correct
15 Correct 287 ms 186436 KB Output is correct
16 Correct 275 ms 186704 KB Output is correct
17 Correct 196 ms 186288 KB Output is correct
18 Correct 206 ms 186464 KB Output is correct
19 Correct 275 ms 186284 KB Output is correct
20 Correct 304 ms 186336 KB Output is correct