Submission #163661

#	Time	Username	Problem	Language	Result	Execution time	Memory
163661		tselmegkh	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	2075 ms	68436 KiB

apple

#include<bits/stdc++.h>
using namespace std;

const int N = 1e9 + 5;
map<int, int> tree;
map<int, bool> lazy;

void update(int v, int l, int r, int ql, int qr){
	if(lazy[v]){
		lazy[v * 2] = lazy[v * 2 + 1] = 1;
		lazy[v] = 0;
		tree[v] = (r - l) + 1;
	}
	if(ql > r || qr < l)return;
	if(ql <= l && qr >= r){
		tree[v] = (r - l) + 1;
		lazy[v * 2] = lazy[v * 2 + 1] = 1;
		return;
	}
	int mid = (l + r) / 2;
	update(v * 2, l, mid, ql, qr);
	update(v * 2 + 1, mid + 1, r, ql, qr);
	tree[v] = tree[v * 2] + tree[v * 2 + 1];
}

int query(int v, int l, int r, int ql, int qr){
	if(lazy[v]){
		tree[v] = (r - l) + 1;
		lazy[v * 2] = lazy[v * 2 + 1] = 1;
		lazy[v] = 0;
	}
	if(qr < l || ql > r)return 0;
	if(ql <= l && qr >= r){
		return tree[v];
	}
	int mid = (l + r) / 2;
	return query(v * 2, l, mid, ql, qr) + query(v * 2 + 1, mid + 1, r, ql, qr);
}

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

	while(q--){
		int type, x, y;
		cin >> type >> x >> y;
		if(type == 1){
			int res = query(1, 1, N, x + c, y + c);
			cout << res << '\n';
			c = res;
		}else{
			update(1, 1, N, x + c, y + c);
		}
	}
}

• Subtask 1: 0 / 100