Submission #737614

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
737614	2023-05-07T12:31:06 Z	happypotato	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	473 ms	205568 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
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);
void pushdown(node *cur) {
	int mid = (cur->l + cur->r) >> 1;
	if (cur->left == nullptr) cur->left = new node(cur->l, mid);
	if (cur->right == nullptr) cur->right = new node(mid + 1, cur->r);
	if (cur->all) {
		cur->left->ans = mid - cur->l + 1;
		cur->left->all = true;
		cur->right->ans = cur->r - mid;
		cur->right->all = true;
	}
}
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;
	}
	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;
	}
	pushdown(cur);
	int mid = (cur->l + cur->r) >> 1;
	int res = 0;
	if (tl <= mid) res += query(tl, tr, cur->left);
	if (tr > mid) res += query(tl, tr, cur->right);
	return res;
}
void init() {
	// initialize
	
}
void solve(int &case_no) {
	// solve
	int q;
	cin >> q;
	int C = 0;
	while (q--) {
		int cmd, l, r;
		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	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	18 ms	4824 KB	Output is correct
5	Correct	24 ms	5784 KB	Output is correct
6	Correct	21 ms	5596 KB	Output is correct
7	Correct	21 ms	5848 KB	Output is correct
8	Correct	148 ms	43688 KB	Output is correct
9	Correct	312 ms	75568 KB	Output is correct
10	Correct	305 ms	83704 KB	Output is correct
11	Correct	317 ms	89888 KB	Output is correct
12	Correct	311 ms	92740 KB	Output is correct
13	Correct	317 ms	107932 KB	Output is correct
14	Correct	300 ms	108912 KB	Output is correct
15	Correct	473 ms	199528 KB	Output is correct
16	Correct	443 ms	201040 KB	Output is correct
17	Correct	322 ms	112660 KB	Output is correct
18	Correct	327 ms	112724 KB	Output is correct
19	Correct	436 ms	205568 KB	Output is correct
20	Correct	453 ms	205480 KB	Output is correct