#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
/*
const int INF = 2e9;
struct SegTree{
struct node{
int mini1,mini2;
int maxi1,maxi2;
int minlazy,maxlazy;
node():mini1(0),mini2(INF),maxi1(0),maxi2(-INF),minlazy(INF),maxlazy(-INF){}
void setmax(int x){
if(x <= mini1)
return;
if(maxi1 == mini1)
maxi1 = x;
if(maxi2 == mini1)
maxi2 = x;
mini1 = maxlazy = x;
}
void setmin(int x){
if(x >= maxi1)
return;
if(mini1 == maxi1)
mini1 = x;
if(mini2 == maxi1)
mini2 = x;
maxi1 = minlazy = x;
}
};
node merge(node a,node b){
if(a.maxi1 < b.maxi1){
a.maxi2 = a.maxi1;
a.maxi1 = b.maxi1;
}
if(a.maxi1 == b.maxi1){
a.maxi2 = max(a.maxi2,b.maxi2);
}
else{
a.maxi2 = max(a.maxi2,b.maxi1);
}
if(a.mini1 > b.mini1){
a.mini2 = a.mini1;
a.mini1 = b.mini1;
}
if(a.mini1 == b.mini1){
a.mini2 = min(a.mini2,b.mini2);
}
else{
a.mini2 = min(a.mini2,b.mini1);
}
a.maxlazy = -INF;
a.minlazy = INF;
return a;
}
vector<node> t;
int n;
SegTree(int sz){
n = sz;
t.assign(4*n,node());
}
void push(int v){
t[v*2].setmax(t[v].maxlazy);
t[v*2].setmin(t[v].minlazy);
t[v*2 + 1].setmax(t[v].maxlazy);
t[v*2 + 1].setmin(t[v].minlazy);
t[v].maxlazy = -INF;
t[v].minlazy = INF;
}
void upd(int v,int tl,int tr,int l,int r,int val,int op){
if(tr < l || r < tl || (op == 1 && t[v].mini1 >= val) || (op == 2 && t[v].maxi1 <= val)){
return;
}
if(l <= tl && tr <= r && ((op == 1 && t[v].mini2 > val) || (op == 2 && t[v].maxi2 < val))){
if(op == 1){
t[v].setmax(val);
}
else t[v].setmin(val);
return;
}
push(v);
int tm = (tl + tr)/2;
upd(v*2,tl,tm,l,r,val,op);
upd(v*2 + 1,tm+1,tr,l,r,val,op);
t[v] = merge(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int pos){
if(tl == tr){
return t[v].maxi1;
}
push(v);
int tm = (tl + tr)/2;
if(pos <= tm){
return get(v*2,tl,tm,pos);
}
return get(v*2+1,tm+1,tr,pos);
}
void upd(int l,int r,int val,int op){
upd(1,0,n-1,l,r,val,op);
}
int get(int pos){
return get(1,0,n-1,pos);
}
};
*/
const int INF = INT_MAX;
struct info {
int mx1, mx2, mx_cnt, mn1, mn2, mn_cnt;
info(int a = -INF, int b = -INF, int c = 0, int d = INF, int e = INF, int f = 0) {
mx1 = a, mx2 = b, mx_cnt = c, mn1 = d, mn2 = e, mn_cnt = f;
}
friend inline info merge(info u, info v) {
if (u.mx1 < v.mx1) {
u.mx_cnt = 0;
u.mx2 = u.mx1;
u.mx1 = v.mx1;
}
if (u.mx1 == v.mx1) {
u.mx_cnt += v.mx_cnt;
u.mx2 = max(u.mx2, v.mx2);
}
else
u.mx2 = max(u.mx2, v.mx1);
if (u.mn1 > v.mn1) {
u.mn_cnt = 0;
u.mn2 = u.mn1;
u.mn1 = v.mn1;
}
if (u.mn1 == v.mn1) {
u.mn_cnt += v.mn_cnt;
u.mn2 = min(u.mn2, v.mn2);
}
else
u.mn2 = min(u.mn2, v.mn1);
return u;
}
};
struct node {
info p;
long long sum;
int mx_lazy, mn_lazy;
node(info a = info(), long long b = 0) {
p = a, sum = b, reset();
}
inline void reset() {
mx_lazy = -INF, mn_lazy = INF;
}
inline void set_max(int x) {
if (x <= p.mn1)
return;
sum += 1LL * (x - p.mn1) * p.mn_cnt;
if (p.mx1 == p.mn1)
p.mx1 = x;
if (p.mx2 == p.mn1)
p.mx2 = x;
p.mn1 = mx_lazy = x;
}
inline void set_min(int x) {
if (x >= p.mx1)
return;
sum += 1LL * (x - p.mx1) * p.mx_cnt;
if (p.mn1 == p.mx1)
p.mn1 = x;
if (p.mn2 == p.mx1)
p.mn2 = x;
p.mx1 = mn_lazy = x;
}
friend inline node merge(node u, node v) {
u.p = merge(u.p, v.p);
u.sum += v.sum;
u.reset();
return u;
}
};
const int N = 2e5;
node seg[N << 2];
int n, q, a[N];
inline void find(int id) {
seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}
inline void shift(int id) {
for (auto p: {id << 1, id << 1 | 1}) {
seg[p].set_max(seg[id].mx_lazy);
seg[p].set_min(seg[id].mn_lazy);
}
seg[id].reset();
}
void build(int id = 1, int st = 0, int en = n) {
if (en - st == 1) {
info x;
x.mx1 = a[st], x.mx_cnt = 1;
x.mn1 = a[st], x.mn_cnt = 1;
seg[id] = {x, a[st]};
return;
}
int mid = st + en >> 1;
build(id << 1, st, mid);
build(id << 1 | 1, mid, en);
find(id);
}
void update_max(int l, int r, int x, int id = 1, int st = 0, int en = n) {
if (r <= st || en <= l || seg[id].p.mn1 >= x)
return;
if (l <= st && en <= r && seg[id].p.mn2 > x)
return seg[id].set_max(x);
shift(id);
int mid = st + en >> 1;
update_max(l, r, x, id << 1, st, mid);
update_max(l, r, x, id << 1 | 1, mid, en);
find(id);
}
void update_min(int l, int r, int x, int id = 1, int st = 0, int en = n) {
if (r <= st || en <= l || seg[id].p.mx1 <= x)
return;
if (l <= st && en <= r && seg[id].p.mx2 < x)
return seg[id].set_min(x);
shift(id);
int mid = st + en >> 1;
update_min(l, r, x, id << 1, st, mid);
update_min(l, r, x, id << 1 | 1, mid, en);
find(id);
}
long long get(int l, int r, int id = 1, int st = 0, int en = n) {
if (r <= st || en <= l)
return 0;
if (l <= st && en <= r)
return seg[id].sum;
shift(id);
int mid = st + en >> 1;
return get(l, r, id << 1, st, mid) + get(l, r, id << 1 | 1, mid, en);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
::n = n;
build();
for(int i = 0;i<k;i++){
if(op[i] == 1){
update_max(left[i],right[i] + 1,height[i]);
}
else{
update_min(left[i],right[i] + 1,height[i]);
}
}
for(int i = 0;i<n;i++){
finalHeight[i] = get(i,i + 1);
}
}
Compilation message
wall.cpp: In function 'void build(int, int, int)':
wall.cpp:201:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
201 | int mid = st + en >> 1;
| ~~~^~~~
wall.cpp: In function 'void update_max(int, int, int, int, int, int)':
wall.cpp:213:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
213 | int mid = st + en >> 1;
| ~~~^~~~
wall.cpp: In function 'void update_min(int, int, int, int, int, int)':
wall.cpp:225:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
225 | int mid = st + en >> 1;
| ~~~^~~~
wall.cpp: In function 'long long int get(int, int, int, int, int)':
wall.cpp:237:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
237 | int mid = st + en >> 1;
| ~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
31572 KB |
Output is correct |
| 2 |
Correct |
16 ms |
31624 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
31572 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
31504 KB |
Output is correct |
| 2 |
Correct |
126 ms |
40644 KB |
Output is correct |
| 3 |
Correct |
75 ms |
36172 KB |
Output is correct |
| 4 |
Correct |
176 ms |
41416 KB |
Output is correct |
| 5 |
Correct |
185 ms |
41772 KB |
Output is correct |
| 6 |
Correct |
220 ms |
41788 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
31572 KB |
Output is correct |
| 2 |
Correct |
16 ms |
31760 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
31636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
31620 KB |
Output is correct |
| 2 |
Correct |
16 ms |
31756 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
31636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
