oj.uz

Submission #786367

# Submission time Handle Problem Language Result Execution time Memory
786367 2023-07-18T07:07:27 Z 이동현(#10029) Weirdtree (RMI21_weirdtree) C++17
100 / 100
 821 ms 67680 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

const int NS = (int)3e5 + 4;
int n, q;
int ini[NS];
long long sum[NS * 4];
vector<int> mx[NS * 4];

vector<int> merge(vector<int> x, vector<int> y){
	if(x[0] < y[0]) swap(x, y);
	if(x[0] == y[0]){
		if(x[2] == y[2]) return {x[0], x[1] + y[1], x[2], x[3] + y[3]};
		else if(x[2] > y[2]) return {x[0], x[1] + y[1], x[2], x[3]};
		else return {x[0], x[1] + y[1], y[2], y[3]};
	}
	if(x[2] == y[0]) return {x[0], x[1], x[2], x[3] + y[1]};
	else if(x[2] > y[0]) return x;
	return {x[0], x[1], y[0], y[1]};
}

void dolazy(int x, int s, int e){
	if(s == e) return;
	if(mx[x * 2][0] > mx[x][0]){
		sum[x * 2] -= (long long)mx[x * 2][1] * (mx[x * 2][0] - mx[x][0]);
		mx[x * 2][0] = mx[x][0];
	}
	if(mx[x * 2 + 1][0] > mx[x][0]){
		sum[x * 2 + 1] -= (long long)mx[x * 2 + 1][1] * (mx[x * 2 + 1][0] - mx[x][0]);
		mx[x * 2 + 1][0] = mx[x][0];
	}
}

void upd(int x, int s, int e, int val){
	if(val >= mx[x][0]) return;

	dolazy(x, s, e);
	
	if(!mx[x][2] || val > mx[x][2]){
		sum[x] -= (long long)(mx[x][0] - val) * mx[x][1];
		mx[x][0] = val;

		dolazy(x, s, e);

		return;
	}
	int m = s + e >> 1;
	upd(x * 2, s, m, val);
	upd(x * 2 + 1, m + 1, e, val);
	
	sum[x] = sum[x * 2] + sum[x * 2 + 1];
	mx[x] = merge(mx[x * 2], mx[x * 2 + 1]);
}

void build(int x, int s, int e){
	if(s == e){
		mx[x] = {ini[s], 1, 0, 0};
		sum[x] = ini[s];
		return;
	}

	int m = s + e >> 1;
	build(x * 2, s, m), build(x * 2 + 1, m + 1, e);
	mx[x] = merge(mx[x * 2], mx[x * 2 + 1]);
	sum[x] = sum[x * 2] + sum[x * 2 + 1];
}

void push(int x, int s, int e, int pos, int val){
	if(s == e){
		mx[x] = {val, 1, 0, 0};
		sum[x] = val;
		return;
	}

	dolazy(x, s, e);

	int m = s + e >> 1;
	if(pos <= m) push(x * 2, s, m, pos, val);
	else push(x * 2 + 1, m + 1, e, pos, val);

	mx[x] = merge(mx[x * 2], mx[x * 2 + 1]);
	sum[x] = sum[x * 2] + sum[x * 2 + 1];
}

long long getsum(int x, int s, int e, int fs, int fe){
	if(fe < s || fs > e) return 0;
	
	dolazy(x, s, e);
	if(fs <= s && fe >= e) return sum[x];

	int m = s + e >> 1;
	return getsum(x * 2, s, m, fs, fe) + getsum(x * 2 + 1, m + 1, e, fs, fe);
}

int cnt, lst;
void pushmin(int x, int s, int e, int ps, int pe, int val){
	if(pe < s || ps > e || mx[x][0] < lst || !cnt) return;
	// cout << "PUSHMIN " << x << ' ' << s << ' ' << e << ' ' << ps << ' ' << pe << ' ' << val << ' ' << cnt << endl;
	dolazy(x, s, e);
	if(ps <= s && pe >= e && cnt >= mx[x][1]){
		cnt -= mx[x][1];
		upd(x, s, e, val);
		// cout << "PMVAL " << x << ' ' << mx[x][0] << ' ' << mx[x][1] << ' ' << mx[x][2] << ' ' << mx[x][3] << endl;
		return;
	}

	int m = s + e >> 1;
	pushmin(x * 2, s, m, ps, pe, val);
	pushmin(x * 2 + 1, m + 1, e, ps, pe, val);

	mx[x] = merge(mx[x * 2], mx[x * 2 + 1]);
	sum[x] = sum[x * 2] + sum[x * 2 + 1];
	// cout << "PMVAL " << x << ' ' << mx[x][0] << ' ' << mx[x][1] << ' ' << mx[x][2] << ' ' << mx[x][3] << endl;
}

vector<int> getmx(int x, int s, int e, int fs, int fe){
	if(fe < s || fs > e) return {0, 0, 0, 0};
	dolazy(x, s, e);
	if(fs <= s && fe >= e){
		return mx[x];
	}

	int m = s + e >> 1;
	return merge(getmx(x * 2, s, m, fs, fe), getmx(x * 2 + 1, m + 1, e, fs, fe));
}

void initialise(int N, int Q, int h[]) {
	n = N;
	q = Q;
	for(int i = 1; i <= n; ++i){
		ini[i] = h[i];
	}

	build(1, 1, n);

	// cout << mx[1][0] << ' ' << mx[1][1] << ' ' << mx[1][2] << ' ' << mx[1][3] << endl;
	// exit(0);
}

void cut(int l, int r, int k) {
	while(k){
		vector<int> rv = getmx(1, 1, n, l, r);
		if(!rv[0]) break;
		lst = rv[0];
		// cout << rv[0] << ' ' << rv[1] << ' ' << rv[2] << ' ' << rv[3] << ' ' << k << endl;
		if((long long)(rv[0] - rv[2]) * rv[1] >= k){
			int div = k / rv[1];
			if(div){
				cnt = rv[1];
				pushmin(1, 1, n, l, r, rv[0] - div);
			}
			if(k % rv[1]){
				lst = rv[0] - div;
				cnt = k % rv[1];
				pushmin(1, 1, n, l, r, rv[0] - div - 1);
			}

			break;
		}
		else{
			k -= (rv[0] - rv[2]) * rv[1];
			cnt = rv[1];
			pushmin(1, 1, n, l, r, rv[2]);
		}
	}
}
void magic(int i, int x) {
	push(1, 1, n, i, x);
}
long long int inspect(int l, int r) {
	return getsum(1, 1, n, l, r);
}

Compilation message

weirdtree.cpp: In function 'void upd(int, int, int, int)':
weirdtree.cpp:51:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |  int m = s + e >> 1;
      |          ~~^~~
weirdtree.cpp: In function 'void build(int, int, int)':
weirdtree.cpp:66:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |  int m = s + e >> 1;
      |          ~~^~~
weirdtree.cpp: In function 'void push(int, int, int, int, int)':
weirdtree.cpp:81:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |  int m = s + e >> 1;
      |          ~~^~~
weirdtree.cpp: In function 'long long int getsum(int, int, int, int, int)':
weirdtree.cpp:95:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |  int m = s + e >> 1;
      |          ~~^~~
weirdtree.cpp: In function 'void pushmin(int, int, int, int, int, int)':
weirdtree.cpp:111:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |  int m = s + e >> 1;
      |          ~~^~~
weirdtree.cpp: In function 'std::vector<int> getmx(int, int, int, int, int)':
weirdtree.cpp:127:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |  int m = s + e >> 1;
      |          ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28628 KB Output is correct
2 Correct 17 ms 28532 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28628 KB Output is correct
2 Correct 17 ms 28532 KB Output is correct
3 Correct 128 ms 38288 KB Output is correct
4 Correct 144 ms 38208 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28600 KB Output is correct
2 Correct 21 ms 28648 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28600 KB Output is correct
2 Correct 21 ms 28648 KB Output is correct
3 Correct 802 ms 67328 KB Output is correct
4 Correct 753 ms 67680 KB Output is correct
5 Correct 781 ms 66816 KB Output is correct
6 Correct 691 ms 66540 KB Output is correct
7 Correct 35 ms 36240 KB Output is correct
8 Correct 111 ms 36244 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 36240 KB Output is correct
2 Correct 111 ms 36244 KB Output is correct
3 Correct 331 ms 58164 KB Output is correct
4 Correct 346 ms 58980 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28628 KB Output is correct
2 Correct 17 ms 28532 KB Output is correct
3 Correct 128 ms 38288 KB Output is correct
4 Correct 144 ms 38208 KB Output is correct
5 Correct 20 ms 28600 KB Output is correct
6 Correct 21 ms 28648 KB Output is correct
7 Correct 35 ms 36240 KB Output is correct
8 Correct 111 ms 36244 KB Output is correct
9 Correct 123 ms 38348 KB Output is correct
10 Correct 142 ms 38164 KB Output is correct
11 Correct 133 ms 38148 KB Output is correct
12 Correct 147 ms 38564 KB Output is correct
13 Correct 140 ms 38604 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28628 KB Output is correct
2 Correct 17 ms 28532 KB Output is correct
3 Correct 128 ms 38288 KB Output is correct
4 Correct 144 ms 38208 KB Output is correct
5 Correct 20 ms 28600 KB Output is correct
6 Correct 21 ms 28648 KB Output is correct
7 Correct 802 ms 67328 KB Output is correct
8 Correct 753 ms 67680 KB Output is correct
9 Correct 781 ms 66816 KB Output is correct
10 Correct 691 ms 66540 KB Output is correct
11 Correct 331 ms 58164 KB Output is correct
12 Correct 346 ms 58980 KB Output is correct
13 Correct 123 ms 38348 KB Output is correct
14 Correct 142 ms 38164 KB Output is correct
15 Correct 133 ms 38148 KB Output is correct
16 Correct 147 ms 38564 KB Output is correct
17 Correct 140 ms 38604 KB Output is correct
18 Correct 35 ms 36240 KB Output is correct
19 Correct 111 ms 36244 KB Output is correct
20 Correct 691 ms 65204 KB Output is correct
21 Correct 821 ms 66984 KB Output is correct
22 Correct 726 ms 66620 KB Output is correct
23 Correct 781 ms 66576 KB Output is correct
24 Correct 697 ms 66000 KB Output is correct