Submission #399274

#	Time	Username	Problem	Language	Result	Execution time	Memory
399274		sinamhdv	Monkey and Apple-trees (IZhO12_apple)	C++11	100 / 100	444 ms	139420 KiB

apple

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 100100

struct node
{
	node *lc, *rc;
	int sum, lz;
};

int q;
node rt;

inline void mkcld(node *v)
{
	if (v -> lc == NULL) v->lc = new node();
	if (v -> rc == NULL) v->rc = new node();
}

inline void pushdown(node *v, int l, int r)
{
	if (!v -> lz) return;
	v -> lc -> lz = v -> rc -> lz = 1;
	int mid = (r + l) / 2;
	v -> lc -> sum = mid - l + 1;
	v -> rc -> sum = r - mid;
	v -> lz = 0;
}

void rset(int L, int R, node *v = &rt, int l = 0, int r = INF)
{
	if (l > R || r < L) return;
	if (l >= L && r <= R)
	{
		v -> lz = 1;
		v -> sum = (r - l + 1);
		return;
	}
	int mid = (r + l) / 2;
	mkcld(v);
	pushdown(v, l, r);
	rset(L, R, v->lc, l, mid);
	rset(L, R, v->rc, mid + 1, r);
	v -> sum = v -> lc -> sum + v -> rc -> sum;
}

int get(int L, int R, node* v = &rt, int l = 0, int r = INF)
{
	if (l > R || r < L) return 0;
	if (l >= L && r <= R) return v -> sum;
	int mid = (r + l) / 2;
	mkcld(v);
	pushdown(v, l, r);
	return get(L, R, v -> lc, l, mid) + get(L, R, v -> rc, mid + 1, r);
}

int32_t main(void)
{
	fast_io;
	cin >> q;
	int last = 0;
	while (q--)
	{
		int t, x, y;
		cin >> t >> x >> y;
		x += last, y += last;
		if (t == 1)	// ask
			cout << (last = get(x, y)) << endl;
		else	// update
			rset(x, y);
	}
	return 0;
}

• Subtask 1: 100 / 100