Submission #163659

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
163659	2019-11-14T13:47:46 Z	tselmegkh	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	2000 ms	94180 KB

apple

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

const int N = 1e9 + 5;
unordered_map<int, int> tree;
unordered_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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	504 KB	Output is correct
2	Correct	3 ms	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	207 ms	12196 KB	Output is correct
5	Correct	310 ms	17728 KB	Output is correct
6	Correct	304 ms	17740 KB	Output is correct
7	Correct	314 ms	17980 KB	Output is correct
8	Execution timed out	2065 ms	94180 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-