Submission #469353

# Submission time Handle Problem Language Result Execution time Memory
469353 2021-08-31T15:20:14 Z DiTenix Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
1 ms 204 KB
#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define sz(x) int((x).size())
#define ALL(x) (x).begin(),(x).end()
#define ln cout << '\n'
#define REP(i, a) for (int i = 0; i < int(a); i++)
#define FOR(i, a) for (int i = 1; i <= int(a); i++)
#define _ok(x, y) (x >= 0 && x < n && y >= 0 && y < m)
#define MEM(a,b) memset((a),(b),sizeof(a))
const int INF = 0x3f3f3f3f, MOD = 1e9 + 7;
using namespace std;
#include <bits/stdc++.h>
using ll = long long;
using vi = vector<int>;
template<typename T> void writeln(vector<T> &a) {for (auto &ele : a) cout << ele << ' '; cout << "\n";}
#if __cplusplus > 201402L
template<typename... Args> void rd(Args&... args) {((cin >> args), ...);}
template<typename... Args> void write(Args... args) {((cout << args << " "), ...);}
template<typename... Args> void writeln(Args... args) {((cout << args << " "), ...); cout << "\n";}
#endif
const int maxn = 1e5 + 5;;
struct segtree {
	struct node {
		int val, l, r;
	} t[maxn * 40];
	int d[maxn * 40];
	int cnt = 1, root = 1;
	int new_node(int val = 0) {
		t[++cnt].val = val;
		if (val) d[cnt] = 1;
		return cnt;
	}
	void propagate(int l, int r, int x) {
		if (!d[x] || l == r) return;
		int m = (l + r) >> 1;
		if (!t[x].l) {
			t[x].l = new_node(m - l + 1);
			t[x].r = new_node(r - m);
		}
		d[x] = 0;
	}
	void set(int l, int r, int x, int L, int R) {
		if (l > R || r < L) return;
		propagate(l, r, x);
		if (l >= L && r <= R) {
			t[x].val = r - l + 1;
			d[x] = 1;
			return;
		}
		if (!t[x].l) {
			t[x].l = ++cnt; t[x].r = ++cnt;
		}
		int m = (l + r) >> 1;
		set(l, m, t[x].l, L, R);
		set(m + 1, r, t[x].r, L, R);
		t[x].val = t[t[x].l].val + t[t[x].r].val;
	}
	int qry(int l, int r, int x, int L, int R) {
		if (l > R || r < L || !x) return 0;
		propagate(l, r, x);
		if (l >= L && r <= R) {
			return t[x].val;
		}
		int m = (l + r) >> 1;
		return qry(l, m, t[x].l, L, R) + qry(m + 1, r, t[x].r, L, R);
	}
} st;


signed main()
{
/*#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif*/
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(false);
//	int t;cin >> t;while(t--) solve();
	int m;
	cin >> m;
	int lastans = 0;
	const int R = 1000'000'000;
	while (m--) {
		int op, l, r;
		cin >> op >> l >> r;
		l += lastans;
		r += lastans;
		if (op == 1) {
			int res = st.qry(1, R, 1, l, r);
			cout << res << "\n";
			lastans = res;
		} else {
			st.set(1, R, 1, l, r);
		}
	}
	/*FOR(i, st.cnt) {
		writeln(i, st.t[i].val);
	}*/
	return 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 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -