oj.uz

Submission #786765

# Submission time Handle Problem Language Result Execution time Memory
786765 2023-07-18T12:40:54 Z qwerasdfzxcl Weirdtree (RMI21_weirdtree) C++17
100 / 100
 566 ms 29608 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 1e9 + 100;

int n;

struct Node{
	int mx, smx, cnt;
	Node(){}
	Node(int x):mx(x), smx(0), cnt(1) {}
	Node(int _mx, int _smx, int _cnt): mx(_mx), smx(_smx), cnt(_cnt){}

	Node operator + (const Node &N) const{
		Node ret;
		if (mx > N.mx) ret.mx = mx, ret.smx = max(N.mx, smx), ret.cnt = cnt;
		else if (mx < N.mx) ret.mx = N.mx, ret.smx = max(mx, N.smx), ret.cnt = N.cnt;
		else ret.mx = mx, ret.smx = max(smx, N.smx), ret.cnt = cnt + N.cnt;

		return ret;
	}
};

struct Seg{
	Node tree[1201200];
	ll tree2[1201200];

	int lazy[1201200];

	void init(int i, int l, int r, int a[]){
		lazy[i] = INF;
		if (l==r){
			tree[i] = Node(a[l]);
			tree2[i] = a[l];
			return;
		}

		int m = (l+r)>>1;
		init(i<<1, l, m, a); init(i<<1|1, m+1, r, a);
		tree[i] = tree[i<<1] + tree[i<<1|1];
		tree2[i] = tree2[i<<1] + tree2[i<<1|1];
	}

	void propagate(int i, int l, int r){
		if (lazy[i]==INF) return;
		
		int d = tree[i].mx - min(tree[i].mx, lazy[i]);
		tree2[i] -= (ll)d * tree[i].cnt;
		tree[i].mx = min(tree[i].mx, lazy[i]);

		assert(tree[i].mx > tree[i].smx || tree[i].mx==0);

		if (l!=r){
			lazy[i<<1] = min(lazy[i<<1], lazy[i]);
			lazy[i<<1|1] = min(lazy[i<<1|1], lazy[i]);
		}

		lazy[i] = INF;
	}

	void updateM(int i, int l, int r, int s, int e, int x){
		propagate(i, l, r);
		if (r<s || e<l) return;
		if (s<=l && r<=e && (x > tree[i].smx || (x==0 && tree[i].smx==0))){
			lazy[i] = x;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		updateM(i<<1, l, m, s, e, x); updateM(i<<1|1, m+1, r, s, e, x);
		tree[i] = tree[i<<1] + tree[i<<1|1];
		tree2[i] = tree2[i<<1] + tree2[i<<1|1];
	}

	void updateV(int i, int l, int r, int p, int x){
		propagate(i, l, r);
		if (r<p || p<l) return;
		if (l==r){
			tree[i] = Node(x);
			tree2[i] = x;
			return;
		}

		int m = (l+r)>>1;
		updateV(i<<1, l, m, p, x); updateV(i<<1|1, m+1, r, p, x);
		tree[i] = tree[i<<1] + tree[i<<1|1];
		tree2[i] = tree2[i<<1] + tree2[i<<1|1];
	}

	int prefix(int i, int l, int r, int s, int val, int cnt){
		// printf(" call %d %d %d %d %d %d\n", i, l, r, s, val, cnt);
		propagate(i, l, r);
		if (r<s) return 0;
		if (s<=l){
			if (tree[i].mx < val) return 0;
			if (tree[i].mx==val && tree[i].cnt < cnt) return -tree[i].cnt;
			if (l==r){
				if (tree[i].mx == val) return l;
				else return 0;
			} 
		}
		
		int m = (l+r)>>1;
		int ret1 = prefix(i<<1, l, m, s, val, cnt);
		if (ret1 > 0) return ret1;

		cnt += ret1;
		int ret2 = prefix(i<<1|1, m+1, r, s, val, cnt);
		if (ret2 > 0) return ret2;
		return ret1 + ret2;
	}

	Node query(int i, int l, int r, int s, int e){
		propagate(i, l, r);
		if (r<s || e<l) return Node(0, 0, 0);
		if (s<=l && r<=e) return tree[i];

		int m = (l+r)>>1;
		return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, s, e);
	}

	ll sum(int i, int l, int r, int s, int e){
		propagate(i, l, r);
		if (r<s || e<l) return 0;
		if (s<=l && r<=e) return tree2[i];

		int m = (l+r)>>1;
		return sum(i<<1, l, m, s, e) + sum(i<<1|1, m+1, r, s, e);
	}
}tree;

void initialise(int N, int Q, int h[]) {
	n = N;
	tree.init(1, 1, n, h);
}

void cut(int l, int r, int k) {
	while(k > 0){
		auto N = tree.query(1, 1, n, l, r);
		// printf("ok %d %d cnt = %d / k = %d\n", N.mx, N.smx, N.cnt, k);
		if (k >= (ll)N.cnt * (N.mx - N.smx)){
			k -= (ll)N.cnt * (N.mx - N.smx);
			tree.updateM(1, 1, n, l, r, N.smx);

			if (N.smx==0) return;
		}

		else{
			int quo = k / N.cnt, rem = k % N.cnt;
			int idx = l-1;
			if (rem > 0) idx = tree.prefix(1, 1, n, l, N.mx, rem);

			// printf(" okok idx = %d\n", idx);
			
			if (l<=idx) tree.updateM(1, 1, n, l, idx, N.mx-quo-1);
			if (idx+1<=r) tree.updateM(1, 1, n, idx+1, r, N.mx-quo);
			return;
		}
	}
}

void magic(int i, int x) {
	tree.updateV(1, 1, n, i, x);
}

long long int inspect(int l, int r) {
	return tree.sum(1, 1, n, l, r);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 66 ms 7796 KB Output is correct
4 Correct 87 ms 7928 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 566 ms 29360 KB Output is correct
4 Correct 404 ms 29584 KB Output is correct
5 Correct 564 ms 29608 KB Output is correct
6 Correct 463 ms 29388 KB Output is correct
7 Correct 9 ms 7252 KB Output is correct
8 Correct 52 ms 7024 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7252 KB Output is correct
2 Correct 52 ms 7024 KB Output is correct
3 Correct 143 ms 27940 KB Output is correct
4 Correct 172 ms 28012 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 66 ms 7796 KB Output is correct
4 Correct 87 ms 7928 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 9 ms 7252 KB Output is correct
8 Correct 52 ms 7024 KB Output is correct
9 Correct 66 ms 7676 KB Output is correct
10 Correct 107 ms 7612 KB Output is correct
11 Correct 70 ms 7604 KB Output is correct
12 Correct 85 ms 7688 KB Output is correct
13 Correct 70 ms 7636 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 66 ms 7796 KB Output is correct
4 Correct 87 ms 7928 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 566 ms 29360 KB Output is correct
8 Correct 404 ms 29584 KB Output is correct
9 Correct 564 ms 29608 KB Output is correct
10 Correct 463 ms 29388 KB Output is correct
11 Correct 143 ms 27940 KB Output is correct
12 Correct 172 ms 28012 KB Output is correct
13 Correct 66 ms 7676 KB Output is correct
14 Correct 107 ms 7612 KB Output is correct
15 Correct 70 ms 7604 KB Output is correct
16 Correct 85 ms 7688 KB Output is correct
17 Correct 70 ms 7636 KB Output is correct
18 Correct 9 ms 7252 KB Output is correct
19 Correct 52 ms 7024 KB Output is correct
20 Correct 360 ms 28428 KB Output is correct
21 Correct 535 ms 28552 KB Output is correct
22 Correct 379 ms 28524 KB Output is correct
23 Correct 497 ms 28536 KB Output is correct
24 Correct 409 ms 28500 KB Output is correct