Submission #954971

#	Time	Username	Problem	Language	Result	Execution time	Memory
954971		hanifchdn	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	284 ms	204624 KiB

apple

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 1e5 + 5;

struct node {
	int sum, lazy, l, r;
	node() : sum(0), lazy(0), l(-1), r(-1) {}
};

node st[64 * N];
int cnt = 1;

void push(int x, int tl, int tr) {
	if (!st[x].lazy) return;
	st[x].sum = tr - tl + 1;
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[x].r = ++cnt;
	}
	st[st[x].l].lazy = st[x].lazy;
	st[st[x].r].lazy = st[x].lazy;
	st[x].lazy = 0;
}

void update(int x, int tl, int tr, int l, int r) {
	push(x, tl, tr);
	int tm = (tl + tr) / 2;
	if (l <= tl and tr <= r) {
		st[x].lazy = 1;
		push(x, tl, tr);
		return;
	}
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[x].r = ++cnt;
	}
	if (r > tm) update(st[x].r, tm + 1, tr, l, r);
	if (l <= tm) update(st[x].l, tl, tm, l, r);
	push(st[x].l, tl, tm);
	push(st[x].r, tm + 1, tr);
	st[x].sum = st[st[x].l].sum + st[st[x].r].sum;
}

int get(int x, int tl, int tr, int l, int r) {
	push(x, tl, tr);
	int tm = (tl + tr) / 2;
	if (l <= tl and tr <= r) return st[x].sum;
	int res = 0;
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[x].r = ++cnt;
	}
	if (r > tm) res += get(st[x].r, tm + 1, tr, l, r);
	if (l <= tm) res += get(st[x].l, tl, tm, l, r);
	return res;
}

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int q;
    cin >> q;
    int c = 0;
    while (q--) {
    	int d, x, y;
    	cin >> d >> x >> y;
    	if (d == 1) {
    		c = get(1, 1, 1e9, x + c, y + c);
    		cout << c << "\n";
    	}
    	else {
    		update(1, 1, 1e9, x + c, y + c);
    	}
    }	
}  

• Subtask 1: 0 / 100