oj.uz

Submission #573492

# Submission time Handle Problem Language Result Execution time Memory
573492 2022-06-06T17:44:44 Z vovamr Weirdtree (RMI21_weirdtree) C++17
100 / 100
 345 ms 49052 KB 
#include <bits/stdc++.h>
#include "weirdtree.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 = 1e12; 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); }

int n;
const int N = 3e5 + 100;

struct node {
	ll s, mx, smx, cmx;
	node(int x = 0) : s(x), mx(x) { cmx = 1; smx = -inf; }
} t[4 * N];
inline node merge(const node &a, const node &b) {
	node res;
	res.s = a.s + b.s;
	res.mx = max(a.mx, b.mx);
	res.cmx = (a.mx == res.mx ? a.cmx : 0) + (b.mx == res.mx ? b.cmx : 0);
	res.smx = max(a.smx, b.smx);
	if (a.mx != res.mx) chmax(res.smx, a.mx);
	if (b.mx != res.mx) chmax(res.smx, b.mx);
	return res;
}
inline void mg(int v) { t[v] = merge(t[2 * v + 1], t[2 * v + 2]); }

inline void cmin(int v, int x) {
	if (t[v].mx > x) {
		t[v].s -= (t[v].mx - x) * 1ll * t[v].cmx;
		t[v].mx = x;
	}
}
inline void push(int v) {
	for (int u : {2 * v + 1, 2 * v + 2}) {
		cmin(u, t[v].mx);
	}
}

inline void build(int v, int vl, int vr, int *h) {
	if (vl == vr) return void(t[v] = node(h[vl + 1]));
	int m = vl + vr >> 1;
	build(2 * v + 1, vl, m, h);
	build(2 * v + 2, m + 1, vr, h);
	mg(v);
}
inline void uset(int v, int vl, int vr, int pos, int x) {
	if (vl == vr) return void(t[v] = node(x));
	push(v);
	int m = vl + vr >> 1;
	if (pos <= m) uset(2 * v + 1, vl, m, pos, x);
	else uset(2 * v + 2, m + 1, vr, pos, x);
	mg(v);
}
inline void umin(int v, int vl, int vr, int l, int r, int x) {
	if (l > r || t[v].mx <= x) return;
	else if (vl == l && vr == r && t[v].smx < x) {
		cmin(v, x); return;
	}
	push(v);
	int m = vl + vr >> 1;
	umin(2 * v + 1, vl, m, l, min(r, m), x);
	umin(2 * v + 2, m + 1, vr, max(l, m + 1), r, x);
	mg(v);
}
inline void uadd(int v, int vl, int vr, int l, int r, ll need, int &x) {
	if (l > r || !x || t[v].mx < need) return;
	else if (vl == l && vr == r && t[v].mx - 1 > t[v].smx && x >= t[v].cmx) {
		cmin(v, t[v].mx - 1); x -= t[v].cmx;
		return;
	}
	push(v);
	int m = vl + vr >> 1;
	uadd(2 * v + 1, vl, m, l, min(r, m), need, x);
	uadd(2 * v + 2, m + 1, vr, max(l, m + 1), r, need, x);
	mg(v);
}

inline node get(int v, int vl, int vr, int l, int r) {
	if (vl == l && vr == r) return t[v];
	push(v);
	int m = vl + vr >> 1;
	if (r <= m) return get(2 * v + 1, vl, m, l, r);
	else if (l > m) return get(2 * v + 2, m + 1, vr, l, r);
	else {
		node a = get(2 * v + 1, vl, m, l, m);
		node b = get(2 * v + 2, m + 1, vr, m + 1, r);
		return merge(a, b);
	}
}

void initialise(int N, int Q, int h[]) {
	n = N;
	build(0, 0, n - 1, h);
}
void cut(int l, int r, int k) { --l, --r;
	while (k) {
		node cur = get(0, 0, n - 1, l, r);

		if (cur.mx == 0) break;

		if (cur.cmx * (cur.mx - cur.smx) <= k) {
			k -= cur.cmx * (cur.mx - cur.smx);
			umin(0, 0, n - 1, l, r, cur.smx);
		}
		else {
			ll newv = max(0ll, cur.mx - (k / cur.cmx));
			umin(0, 0, n - 1, l, r, newv);
			k %= cur.cmx;
			uadd(0, 0, n - 1, l, r, newv, k);
		}
	}
}
void magic(int i, int x) {
	uset(0, 0, n - 1, --i, x);
}
long long int inspect(int l, int r) {
	return get(0, 0, n - 1, --l, --r).s;
}

#ifdef LOCAL
int main() {
    int N, Q;
    cin >> N >> Q;

    int h[N + 1];

    for (int i = 1; i <= N; ++i) cin >> h[i];

    initialise(N, Q, h);

    for (int i = 1; i <= Q; ++i) {
        int t;
        cin >> t;

        if (t == 1) {
            int l, r, k;
            cin >> l >> r >> k;
            cut(l, r, k);
        } else if (t == 2) {
            int i, x;
            cin >> i >> x;
            magic(i, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << inspect(l, r) << '\n';
        }
    }
    return 0;
}
#endif

Compilation message

weirdtree.cpp: In function 'void build(int, int, int, int*)':
weirdtree.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |  int m = vl + vr >> 1;
      |          ~~~^~~~
weirdtree.cpp: In function 'void uset(int, int, int, int, int)':
weirdtree.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |  int m = vl + vr >> 1;
      |          ~~~^~~~
weirdtree.cpp: In function 'void umin(int, int, int, int, int, int)':
weirdtree.cpp:76:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |  int m = vl + vr >> 1;
      |          ~~~^~~~
weirdtree.cpp: In function 'void uadd(int, int, int, int, int, long long int, int&)':
weirdtree.cpp:88:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |  int m = vl + vr >> 1;
      |          ~~~^~~~
weirdtree.cpp: In function 'node get(int, int, int, int, int)':
weirdtree.cpp:97:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |  int m = vl + vr >> 1;
      |          ~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 37844 KB Output is correct
2 Correct 16 ms 37944 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 37844 KB Output is correct
2 Correct 16 ms 37944 KB Output is correct
3 Correct 66 ms 38788 KB Output is correct
4 Correct 74 ms 38728 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37844 KB Output is correct
2 Correct 20 ms 38020 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37844 KB Output is correct
2 Correct 20 ms 38020 KB Output is correct
3 Correct 345 ms 49052 KB Output is correct
4 Correct 282 ms 48988 KB Output is correct
5 Correct 319 ms 48940 KB Output is correct
6 Correct 276 ms 48804 KB Output is correct
7 Correct 22 ms 38352 KB Output is correct
8 Correct 45 ms 38324 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 38352 KB Output is correct
2 Correct 45 ms 38324 KB Output is correct
3 Correct 109 ms 40876 KB Output is correct
4 Correct 123 ms 40780 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 37844 KB Output is correct
2 Correct 16 ms 37944 KB Output is correct
3 Correct 66 ms 38788 KB Output is correct
4 Correct 74 ms 38728 KB Output is correct
5 Correct 18 ms 37844 KB Output is correct
6 Correct 20 ms 38020 KB Output is correct
7 Correct 22 ms 38352 KB Output is correct
8 Correct 45 ms 38324 KB Output is correct
9 Correct 72 ms 40612 KB Output is correct
10 Correct 71 ms 40680 KB Output is correct
11 Correct 66 ms 40732 KB Output is correct
12 Correct 73 ms 40652 KB Output is correct
13 Correct 67 ms 40704 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 37844 KB Output is correct
2 Correct 16 ms 37944 KB Output is correct
3 Correct 66 ms 38788 KB Output is correct
4 Correct 74 ms 38728 KB Output is correct
5 Correct 18 ms 37844 KB Output is correct
6 Correct 20 ms 38020 KB Output is correct
7 Correct 345 ms 49052 KB Output is correct
8 Correct 282 ms 48988 KB Output is correct
9 Correct 319 ms 48940 KB Output is correct
10 Correct 276 ms 48804 KB Output is correct
11 Correct 109 ms 40876 KB Output is correct
12 Correct 123 ms 40780 KB Output is correct
13 Correct 72 ms 40612 KB Output is correct
14 Correct 71 ms 40680 KB Output is correct
15 Correct 66 ms 40732 KB Output is correct
16 Correct 73 ms 40652 KB Output is correct
17 Correct 67 ms 40704 KB Output is correct
18 Correct 22 ms 38352 KB Output is correct
19 Correct 45 ms 38324 KB Output is correct
20 Correct 255 ms 48220 KB Output is correct
21 Correct 286 ms 48544 KB Output is correct
22 Correct 265 ms 48388 KB Output is correct
23 Correct 273 ms 48540 KB Output is correct
24 Correct 251 ms 48308 KB Output is correct