Submission #300566

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
300566	2020-09-17T09:38:21 Z	Falcon	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	682 ms	242932 KB

apple

#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#ifdef DEBUG
	#include "debug.hpp"
#endif

using namespace std;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
	#define debug(x...) { dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals); }
	#define light_debug(x) { dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0; }
#else
	#define debug(x...)
	#define light_debug(x) 
#endif

template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

template<int n>
class segtree {
	struct node	{
		int s{0};
		bool lzy{false};
		node* l{nullptr}; 
		node* r{nullptr};
	};

	using pnode = node*;

	inline int sum(pnode t) { return t ? t->s : 0; }

	inline void pull(pnode t) { if(t) t->s = sum(t->l) + sum(t->r); }

	inline void push(pnode t, int s, int e) {
		if(t && t->lzy) {
			t->lzy = false;
			t->s = e - s;
			if(!t->l) t->l = new node();
			if(!t->r) t->r = new node();
			t->l->lzy = t->r->lzy = true;
		}
	}

	pnode root{nullptr};

	void update(pnode& t, int s, int e, int l, int r) {
		push(t, s, e);
		
		if(r <= s || e <= l) 
			return;
		
		if(!t) 
			t = new node();
		
		if(l <= s && e <= r) {
			t->lzy = true;
			push(t, s, e);
			return;
		}

		int m = (s + e) >> 1;
		update(t->l, s, m, l, r);
		update(t->r, m, e, l, r);

		pull(t);
	}

	int query(pnode& t, int s, int e, int l, int r) {
		if(!t || r <= s || e <= l) 
			return 0;
		push(t, s, e);
		if(l <= s && e <= r)
			return sum(t);
		int m = (s + e) >> 1;
		return query(t->l, s, m, l, r) + query(t->r, m, e, l, r);
	}

public:

	inline void update(int l, int r) { update(root, 1, n + 1, l, r); }

	inline int query(int l, int r) { return query(root, 1, n + 1, l, r); }

};

constexpr int MAXC = 1'000'000'000;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	#ifdef DEBUG
		freopen("debug", "w", stderr);
	#endif
	
	segtree<MAXC> seg;

	int C{0};

	int M; cin >> M;

	rep(_, M) {
		int D, X, Y; cin >> D >> X >> Y;
		switch(D) {
			case 1:
				cout << (C = seg.query(X + C, Y + C + 1)) << '\n';
				break;
			case 2:
				seg.update(X + C, Y + C + 1);
				break;
		}
	}

	#ifdef DEBUG
		dbg::dout << "\nExecution time: " << clock() << "ms\n";
	#endif

	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	20 ms	5760 KB	Output is correct
5	Correct	25 ms	7040 KB	Output is correct
6	Correct	26 ms	6784 KB	Output is correct
7	Correct	25 ms	7040 KB	Output is correct
8	Correct	211 ms	52216 KB	Output is correct
9	Correct	430 ms	90972 KB	Output is correct
10	Correct	500 ms	100392 KB	Output is correct
11	Correct	491 ms	107712 KB	Output is correct
12	Correct	516 ms	110780 KB	Output is correct
13	Correct	406 ms	128280 KB	Output is correct
14	Correct	415 ms	129912 KB	Output is correct
15	Correct	672 ms	236056 KB	Output is correct
16	Correct	681 ms	237652 KB	Output is correct
17	Correct	418 ms	134392 KB	Output is correct
18	Correct	414 ms	134264 KB	Output is correct
19	Correct	682 ms	242932 KB	Output is correct
20	Correct	669 ms	242680 KB	Output is correct