oj.uz

Submission #684074

# Submission time Handle Problem Language Result Execution time Memory
684074 2023-01-20T09:54:17 Z vovamr Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
 236 ms 71240 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int L = 1;
const int R = 1e9;

const int N = (1e5 + 100) * 33 + 100;
int w = 0;

struct node {
	int l, r, s, push;
} t[4 * N];

inline int node() {
	int v = w++;
	t[v] = {-1, -1, 0, -1};
	return v;
}

inline void push(int v, int vl, int vr) {
	if (t[v].push == -1) return;
	if (!~t[v].l) t[v].l = node();
	if (!~t[v].r) t[v].r = node();

	int m = vl + vr >> 1;
	t[t[v].l].push = t[t[v].r].push = t[v].push;
	t[t[v].l].s = (m - vl + 1) * t[v].push;
	t[t[v].r].s = (vr - m) * t[v].push;
	t[v].push = -1;
}

inline void upd(int &v, int vl, int vr, int l, int r, int x) {
	if (l > r) return;

	if (!~v) v = node();
	if (vl == l && vr == r) {
		t[v].s = x * (vr - vl + 1);
		t[v].push = x;
		return;
	}
	push(v, vl, vr);
	int m = vl + vr >> 1;
	upd(t[v].l, vl, m, l, min(r, m), x);
	upd(t[v].r, m + 1, vr, max(l, m + 1), r, x);
	
	t[v].s = 0;
	if (~t[v].l) t[v].s += t[t[v].l].s;
	if (~t[v].r) t[v].s += t[t[v].r].s;
}
inline int get(int v, int vl, int vr, int l, int r) {
	if (!~v || l > r) return 0;
	else if (vl == l && vr == r) return t[v].s;
	push(v, vl, vr);
	int m = vl + vr >> 1;
	return get(t[v].l, vl, m, l, min(r, m)) +
			get(t[v].r, m + 1, vr, max(l, m + 1), r);
}

inline void solve() {
	int q;
	cin >> q;

	int last = 0;

	int rt = node();

	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int l, r;
			cin >> l >> r;

			l += last;
			r += last;

			last = get(rt, L, R, l, r);
			cout << last << '\n';
		}
		else {
			int l, r;
			cin >> l >> r;

			l += last;
			r += last;

			upd(rt, L, R, l, r, 1);
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message

apple.cpp: In function 'void push(int, int, int)':
apple.cpp:44:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |  int m = vl + vr >> 1;
      |          ~~~^~~~
apple.cpp: In function 'void upd(int&, int, int, int, int, int)':
apple.cpp:61:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  int m = vl + vr >> 1;
      |          ~~~^~~~
apple.cpp: In function 'int get(int, int, int, int, int)':
apple.cpp:73:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |  int m = vl + vr >> 1;
      |          ~~~^~~~

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 10 ms 2004 KB Output is correct
5 Correct 12 ms 2260 KB Output is correct
6 Correct 12 ms 2260 KB Output is correct
7 Correct 12 ms 2264 KB Output is correct
8 Correct 77 ms 15676 KB Output is correct
9 Correct 169 ms 27308 KB Output is correct
10 Correct 207 ms 30016 KB Output is correct
11 Correct 177 ms 32168 KB Output is correct
12 Correct 206 ms 33152 KB Output is correct
13 Correct 191 ms 38536 KB Output is correct
14 Correct 172 ms 38852 KB Output is correct
15 Correct 236 ms 69248 KB Output is correct
16 Correct 214 ms 69712 KB Output is correct
17 Correct 172 ms 40164 KB Output is correct
18 Correct 177 ms 40132 KB Output is correct
19 Correct 223 ms 71240 KB Output is correct
20 Correct 231 ms 71192 KB Output is correct