| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 786358 |
2023-07-18T06:58:19 Z |
이동현(#10029) |
Weirdtree (RMI21_weirdtree) |
C++17 |
|
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;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
28652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
28652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
