oj.uz

Submission #1068468

# Submission time Handle Problem Language Result Execution time Memory
1068468 2024-08-21T10:03:19 Z mickey080929 Weirdtree (RMI21_weirdtree) C++17
100 / 100
 546 ms 44464 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const ll inf = 2e18;

struct Node{
    ll mx, mx2, cnt, sum;
};

Node f(Node u, Node v) {
    if (u.mx == v.mx)
        return {u.mx, max(u.mx2, v.mx2), u.cnt + v.cnt, u.sum + v.sum};
    if (u.mx < v.mx) swap(u, v);
    return {u.mx, max(u.mx2, v.mx), u.cnt, u.sum + v.sum};
}

struct SegmentTree{
	vector<Node> tree;
	void init(ll n) {
		ll sz = 1 << __lg(n-1) + 2;
		tree.assign(sz, {0,0,0,0});
	}
	void push(ll node, ll s, ll e) {
	    if (s == e) return;
	    for (ll i : {node*2, node*2+1}) {
	        if (tree[node].mx < tree[i].mx) {
	            tree[i].sum -= (tree[i].mx - tree[node].mx) * tree[i].cnt;
	            tree[i].mx = tree[node].mx;
	        }
	    }
	}

	void modify(ll node, ll s, ll e, ll tar, ll val) {
		push(node, s, e);
		if (s > tar || tar > e) return;
		if (s == e) {
			tree[node] = {val, -1, 1, val};
			return;
		}
		ll mid = s + e >> 1;
		modify(node*2, s, mid, tar, val);
		modify(node*2+1, mid+1, e, tar, val);
		tree[node] = f(tree[node*2], tree[node*2+1]);
	}

	void update(ll node, ll s, ll e, ll l, ll r, ll v) {
	    push(node, s, e);
	    if (l > e || s > r || tree[node].mx <= v) return;
	    if (l <= s && e <= r && tree[node].mx2 < v) {
	        tree[node].sum -= (tree[node].mx - v) * tree[node].cnt;
	        tree[node].mx = v;
	        push(node, s, e);
	        return;
	    }
	    ll mid = s + e >> 1;
	    update(node*2, s, mid, l, r, v);
	    update(node*2+1, mid+1, e, l, r, v);
	    tree[node] = f(tree[node*2], tree[node*2+1]);
	}

	Node query(ll node, ll s, ll e, ll l, ll r) {
	    push(node, s, e);
	    if (l > e || s > r) return {-1, -1, 0, 0};
	    if (l <= s && e <= r) return tree[node];
	    ll mid = s + e >> 1;
	    return f(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
	}

	pll findLeft(ll node, ll s, ll e, ll l, ll r, ll mx, ll k) {
		push(node, s, e);
		if (l > e || s > r) return {-1, 0};
		if (tree[node].mx < mx) return {-1, 0};
		if (tree[node].mx == mx && tree[node].cnt < k) return {-1, tree[node].cnt};
		if (s == e) return {s, 0};
		ll mid = s + e >> 1;
		pll t1 = findLeft(node*2, s, mid, l, r, mx, k);
		if (t1.first == -1) {
			pll t2 = findLeft(node*2+1, mid+1, e, l, r, mx, k - t1.second);
			return {t2.first, t1.second + t2.second};
		}
		return t1;
	}
};

SegmentTree seg;

ll n;

void initialise(int N, int Q, int h[]) {
	n = N;
	seg.init(N);
	for (ll i=1; i<=N; i++) {
		seg.modify(1, 1, N, i, h[i]);
	}
}

void cut(int l, int r, int _k) {
	ll k = _k;
	while (true) {
		Node ret = seg.query(1, 1, n, l, r);
		if (ret.mx == 0) break;
		ret.mx2 = max(ret.mx2, 0LL);
		if ((ret.mx - ret.mx2) * ret.cnt <= k) {
			seg.update(1, 1, n, l, r, ret.mx2);
			k -= (ret.mx - ret.mx2) * ret.cnt;
			continue;
		}
		ll diff = k / ret.cnt;
		seg.update(1, 1, n, l, r, ret.mx - diff);
		k %= ret.cnt;
		if (k == 0) break;
		ll idx = seg.findLeft(1, 1, n, l, r, ret.mx - diff, k).first;
		assert(idx != -1);
		seg.update(1, 1, n, l, idx, ret.mx - diff - 1);
		break;
	}
}

void magic(int i, int x) {
	seg.modify(1, 1, n, i, x);
}
long long int inspect(int l, int r) {
	return seg.query(1, 1, n, l, r).sum;
}

Compilation message

weirdtree.cpp: In member function 'void SegmentTree::init(ll)':
weirdtree.cpp:24:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   24 |   ll sz = 1 << __lg(n-1) + 2;
      |                ~~~~~~~~~~^~~
weirdtree.cpp: In member function 'void SegmentTree::modify(ll, ll, ll, ll, ll)':
weirdtree.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   ll mid = s + e >> 1;
      |            ~~^~~
weirdtree.cpp: In member function 'void SegmentTree::update(ll, ll, ll, ll, ll, ll)':
weirdtree.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |      ll mid = s + e >> 1;
      |               ~~^~~
weirdtree.cpp: In member function 'Node SegmentTree::query(ll, ll, ll, ll, ll)':
weirdtree.cpp:69:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |      ll mid = s + e >> 1;
      |               ~~^~~
weirdtree.cpp: In member function 'pll SegmentTree::findLeft(ll, ll, ll, ll, ll, ll, ll)':
weirdtree.cpp:79:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |   ll mid = s + e >> 1;
      |            ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 548 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 548 KB Output is correct
3 Correct 72 ms 9300 KB Output is correct
4 Correct 88 ms 9300 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 576 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 576 KB Output is correct
3 Correct 546 ms 44464 KB Output is correct
4 Correct 420 ms 44368 KB Output is correct
5 Correct 505 ms 44380 KB Output is correct
6 Correct 395 ms 44112 KB Output is correct
7 Correct 30 ms 9048 KB Output is correct
8 Correct 74 ms 9052 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 9048 KB Output is correct
2 Correct 74 ms 9052 KB Output is correct
3 Correct 242 ms 35920 KB Output is correct
4 Correct 267 ms 35936 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 548 KB Output is correct
3 Correct 72 ms 9300 KB Output is correct
4 Correct 88 ms 9300 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 576 KB Output is correct
7 Correct 30 ms 9048 KB Output is correct
8 Correct 74 ms 9052 KB Output is correct
9 Correct 73 ms 11348 KB Output is correct
10 Correct 109 ms 11348 KB Output is correct
11 Correct 76 ms 11348 KB Output is correct
12 Correct 99 ms 11476 KB Output is correct
13 Correct 94 ms 11340 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 548 KB Output is correct
3 Correct 72 ms 9300 KB Output is correct
4 Correct 88 ms 9300 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 576 KB Output is correct
7 Correct 546 ms 44464 KB Output is correct
8 Correct 420 ms 44368 KB Output is correct
9 Correct 505 ms 44380 KB Output is correct
10 Correct 395 ms 44112 KB Output is correct
11 Correct 242 ms 35920 KB Output is correct
12 Correct 267 ms 35936 KB Output is correct
13 Correct 73 ms 11348 KB Output is correct
14 Correct 109 ms 11348 KB Output is correct
15 Correct 76 ms 11348 KB Output is correct
16 Correct 99 ms 11476 KB Output is correct
17 Correct 94 ms 11340 KB Output is correct
18 Correct 30 ms 9048 KB Output is correct
19 Correct 74 ms 9052 KB Output is correct
20 Correct 383 ms 43600 KB Output is correct
21 Correct 430 ms 43860 KB Output is correct
22 Correct 373 ms 43856 KB Output is correct
23 Correct 432 ms 43716 KB Output is correct
24 Correct 367 ms 43604 KB Output is correct