oj.uz

답안 #786358

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
786358 2023-07-18T06:58:19 Z 이동현(#10029) Weirdtree (RMI21_weirdtree) C++17
10 / 100
 326 ms 58960 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;
	if(fs <= s && fe >= e) return sum[x];
	
	dolazy(x, s, e);

	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 || !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;
	if(mx[x * 2][0] == lst) pushmin(x * 2, s, m, ps, pe, val);
	if(mx[x * 2 + 1][0] == lst) 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};
	if(fs <= s && fe >= e){
		return mx[x];
	}
	dolazy(x, s, e);

	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]){
				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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 28500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 28500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 28652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 28652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 326 ms 58100 KB Output is correct
2 Correct 324 ms 58960 KB Output is correct
3 Correct 34 ms 36184 KB Output is correct
4 Correct 110 ms 36208 KB Output is correct

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 28500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 28500 KB Output isn't correct
2 Halted 0 ms 0 KB -