Submission #737608

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
737608	2023-05-07T12:27:21 Z	happypotato	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	102 ms	3148 KB

apple

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll int, ll int>
#define ff first
#define ss second
#define pb push_back
#pragma GCC optimize("O2")
using namespace std;
// debug template
#ifdef POTATO
#include "debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
#define debug(...)
#endif
// convenient functions
inline void yes() { cout << "YES" << endl; return; }
inline void no() { cout << "NO" << endl; return; }
template <class T>
inline void out(T temp) { cout << temp << endl; return; }
// globals
#define int long long
struct node {
	int ans, l, r;
	bool all;
	node *left, *right;
	node(int l_, int r_): ans(0), l(l_), r(r_), all(false), left(nullptr), right(nullptr) {};
};
const int MAX = 1e9;
node *seg = new node(1, MAX);
#define mid ((cur->l + cur->r) >> 1)
void pushdown(node *cur) {
	// int mid = (cur->l + cur->r) >> 1;
	if (cur->all) return;
	if (cur->left == nullptr) cur->left = new node(cur->l, mid);
	if (cur->right == nullptr) cur->right = new node(mid + 1, cur->r);
}
void update(int tl, int tr, node *cur = seg) {
	if (tl <= cur->l && cur->r <= tr) {
		cur->ans = (cur->r - cur->l + 1);
		cur->all = true;
		return;
	} else if (cur->all) return;
	pushdown(cur);
	// int mid = (cur->l + cur->r) >> 1;
	if (tl <= mid) update(tl, tr, cur->left);
	if (tr > mid) update(tl, tr, cur->right);
	cur->ans = cur->left->ans + cur->right->ans;
}
int query(int tl, int tr, node *cur = seg) {
	if (tl <= cur->l && cur->r <= tr) {
		return cur->ans;
	} else if (cur->all) {
		return min(tr, cur->r) - max(tl, cur->l) + 1;
	}
	pushdown(cur);
	// int mid = (cur->l + cur->r) >> 1;
	if (tr <= mid) return query(tl, tr, cur->left);
	if (tl > mid) return query(tl, tr, cur->right);
	return query(tl, tr, cur->left) + query(tl, tr, cur->right);
}
void init() {
	// initialize
	
}
void solve(int &case_no) {
	// solve
	int q;
	cin >> q;
	int C = 0;
	int cmd, l, r;
	while (q--) {
		cin >> cmd >> l >> r;
		if (cmd == 1) {
			C = query(l + C, r + C);
			cout << C << endl;
		} else if (cmd == 2) {
			update(l + C, r + C);
		}
	}
}
int32_t main() {
	#ifdef POTATO
	assert(freopen("input.txt", "r", stdin));
	// assert(freopen("output.txt", "w", stdout));
	#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	srand(time(NULL));
	#ifdef POTATO
		auto start = chrono::high_resolution_clock::now();
	#endif

	init();
	int t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++) solve(i);

	#ifdef POTATO
		auto end = chrono::high_resolution_clock::now();
		cerr << "Execution time: "
			<< chrono::duration_cast<chrono::milliseconds>(end - start).count()
			<< " ms" << endl;
	#endif
}
/*

*/

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	9 ms	360 KB	Output is correct
5	Correct	10 ms	360 KB	Output is correct
6	Correct	10 ms	340 KB	Output is correct
7	Correct	10 ms	344 KB	Output is correct
8	Correct	45 ms	456 KB	Output is correct
9	Correct	92 ms	716 KB	Output is correct
10	Correct	91 ms	712 KB	Output is correct
11	Correct	87 ms	704 KB	Output is correct
12	Correct	94 ms	700 KB	Output is correct
13	Correct	102 ms	740 KB	Output is correct
14	Correct	95 ms	848 KB	Output is correct
15	Correct	93 ms	2948 KB	Output is correct
16	Correct	95 ms	2984 KB	Output is correct
17	Correct	86 ms	2872 KB	Output is correct
18	Correct	86 ms	2828 KB	Output is correct
19	Correct	92 ms	3056 KB	Output is correct
20	Correct	96 ms	3148 KB	Output is correct