Submission #737608

#	Time	Username	Problem	Language	Result	Execution time	Memory
737608		happypotato	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	102 ms	3148 KiB

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 / 100