#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];
int lazy[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 upd(int x, int s, int e, int val){
if(!mx[x][2] || val > mx[x][2]){
sum[x] -= (long long)(mx[x][0] - val) * mx[x][1];
mx[x][0] = val;
if(lazy[x] == -1 || lazy[x] > val) lazy[x] = val;
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 dolazy(int x, int s, int e){
if(s == e || lazy[x] == -1) return;
upd(x * 2, s, (s + e) / 2, lazy[x]);
upd(x * 2 + 1, (s + e) / 2 + 1, e, lazy[x]);
lazy[x] = -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) return;
// cout << "PUSHMIN " << x << ' ' << s << ' ' << e << ' ' << ps << ' ' << pe << ' ' << val << ' ' << cnt << endl;
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;
}
dolazy(x, s, e);
int m = s + e >> 1;
if(mx[x * 2][0] == lst) pushmin(x * 2, s, m, ps, pe, val);
if(cnt) 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[]) {
memset(lazy, -1, sizeof(lazy));
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:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int m = s + e >> 1;
| ~~^~~
weirdtree.cpp: In function 'void build(int, int, int)':
weirdtree.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int m = s + e >> 1;
| ~~^~~
weirdtree.cpp: In function 'void push(int, int, int, int, int)':
weirdtree.cpp:71:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | int m = s + e >> 1;
| ~~^~~
weirdtree.cpp: In function 'long long int getsum(int, int, int, int, int)':
weirdtree.cpp:85:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | int m = s + e >> 1;
| ~~^~~
weirdtree.cpp: In function 'void pushmin(int, int, int, int, int, int)':
weirdtree.cpp:102:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
102 | int m = s + e >> 1;
| ~~^~~
weirdtree.cpp: In function 'std::vector<int> getmx(int, int, int, int, int)':
weirdtree.cpp:118:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
118 | int m = s + e >> 1;
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
33236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
33236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2072 ms |
33316 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2072 ms |
33316 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
412 ms |
69588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
33236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
33236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
