Submission #937810

#	Time	Username	Problem	Language	Result	Execution time	Memory
937810		PagodePaiva	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	74 ms	39508 KiB

apple

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

using namespace std;

int tree[4*N], lazy[4*N], L[4*N], R[4*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);
}

int 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: 0 / 100