Submission #399274

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
399274	2021-05-05T13:53:36 Z	sinamhdv	Monkey and Apple-trees (IZhO12_apple)	C++11	100 / 100	444 ms	139420 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	15 ms	3480 KB	Output is correct
5	Correct	16 ms	4164 KB	Output is correct
6	Correct	17 ms	4036 KB	Output is correct
7	Correct	16 ms	4172 KB	Output is correct
8	Correct	147 ms	30092 KB	Output is correct
9	Correct	275 ms	52440 KB	Output is correct
10	Correct	290 ms	57656 KB	Output is correct
11	Correct	281 ms	61908 KB	Output is correct
12	Correct	314 ms	63812 KB	Output is correct
13	Correct	251 ms	74348 KB	Output is correct
14	Correct	271 ms	75020 KB	Output is correct
15	Correct	436 ms	135504 KB	Output is correct
16	Correct	421 ms	136448 KB	Output is correct
17	Correct	269 ms	77428 KB	Output is correct
18	Correct	261 ms	77488 KB	Output is correct
19	Correct	411 ms	139288 KB	Output is correct
20	Correct	444 ms	139420 KB	Output is correct