제출 #937811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937811		PagodePaiva	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	307 ms	202580 KiB

apple

#include<bits/stdc++.h>
#define N 300010
#define int long long

using namespace std;

int tree[40*N], lazy[40*N], L[40*N], R[40*N];
int idx = 1;
int mx = 1e9;

void unlazy(int node, int l, int r){
	if(l == r or !lazy[node]) return;
	// cout << node << ' ' << l << ' ' << r << ' ' << lazy[node] << endl;
	int mid = (l+r)/2;
	if(!L[node]) L[node] = ++idx;
	if(!R[node]) R[node] = ++idx;
	lazy[L[node]] = lazy[R[node]] = lazy[node]; lazy[node] = 0;
	tree[L[node]] = (mid-l+1)*lazy[L[node]];
	tree[R[node]] = (r-mid)*lazy[R[node]];
	return;
}

void update(int node, int l, int r, int tl, int tr, int val){
	if(l > tr or tl > r) return;
	unlazy(node, tl, tr);
	if(l <= tl and tr <= r){
		tree[node] = val*(tr-tl+1);
		lazy[node] = val;
		return;
	}
	int mid = (tl+tr)/2;
	if(l <= mid){
		if(!L[node]) L[node] = ++idx;
		update(L[node], l, r, tl, mid, val);
	}
	if(mid < r){
		if(!R[node]) R[node] = ++idx;
		update(R[node], l, r, mid+1, tr, val);
	}
	tree[node] = tree[L[node]] + tree[R[node]];
}

int query(int node, int l, int r, int tl, int tr){
	if(l > tr or tl > r or !node) return 0;
	unlazy(node, tl, tr);
	if(l <= tl and tr <= r) return tree[node];
	int mid = (tl+tr)/2;
	return query(L[node], l, r, tl, mid) + query(R[node], l, r, mid+1, tr);
}

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int q;
	cin >> q;
	int c = 0;
	while(q--){
		int t, x, y;
		cin >> t >> x >> y;
		x += c;
		y += c;
		if(t == 1){
			c = query(1, x, y, 1, mx);
			cout << c << "\n";
		}
		else{
			update(1, x, y, 1, mx, 1);
		}
	}
	return 0;
}

• Subtask 1: 100 / 100