| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 899413 |
2024-01-06T06:15:42 Z |
ByeWorld |
Wall (IOI14_wall) |
C++14 |
|
98 ms |
15944 KB |
#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 2e6+10;
const int INF = 2e9+10;
int n, k;
int ans[MAXN];
struct node {
int sum;
int mx, mx2, mxc;
int mn, mn2, mnc;
} st[4*MAXN];
struct seg {
void merge(int id){
st[id].sum = st[lf].sum + st[rg].sum;
// mx
if(st[lf].mx == st[rg].mx){
st[id].mx = st[lf].mx;
st[id].mxc = st[lf].mxc + st[rg].mxc;
st[id].mx2 = max(st[lf].mx2, st[rg].mx2);
} else if(st[lf].mx > st[rg].mx){
st[id].mx = st[lf].mx;
st[id].mxc = st[lf].mxc;
st[id].mx2 = max(st[lf].mx2, st[rg].mx);
} else {
// st[lf].mx < st[rg].mx
st[id].mx = st[rg].mx;
st[id].mxc = st[rg].mxc;
st[id].mx2 = max(st[lf].mx, st[rg].mx2);
}
// mn
if(st[lf].mn == st[rg].mn){
st[id].mn = st[lf].mn;
st[id].mnc = st[lf].mnc + st[rg].mnc;
st[id].mn2 = min(st[lf].mn2, st[rg].mn2);
} else if(st[lf].mn < st[rg].mn){
st[id].mn = st[lf].mn;
st[id].mnc = st[lf].mnc;
st[id].mn2 = min(st[lf].mn2, st[rg].mn);
} else {
// st[lf].mn > st[rg].mn
st[id].mn = st[rg].mn;
st[id].mnc = st[rg].mnc;
st[id].mn2 = min(st[lf].mn, st[rg].mn2);
}
}
void bd(int id, int l, int r){
if(l==r){
st[id].sum = st[id].mx = st[id].mn = 0;
st[id].mx2 = -INF; st[id].mn2 = INF;
st[id].mxc = st[id].mnc = 1;
return;
}
bd(lf, l, md); bd(rg, md+1, r);
merge(id);
//cout << l << ' ' << r << ' ' << st[id].mx << ' ' << st[id].mx2 << " lrx\n";
}
void push_mx(int id, int p, bool len){
if(p <= st[id].mn) return;
st[id].sum += (p-st[id].mn) * st[id].mnc; // jadi makin gede
st[id].mn = p;
// mx nya gmn?
if(len){ // l == r
st[id].mx = p;
} else {
if(p >= st[id].mx) st[id].mx = p;
else if(p > st[id].mx2) st[id].mx2 = p;
}
}
void push_mn(int id, int p, bool len){
if(p >= st[id].mx) return;
st[id].sum += (p-st[id].mx) * st[id].mxc; // jadi makin kecil, minus
st[id].mx = p;
// mn nya gmn?
if(len){
st[id].mn = p;
} else {
if(p <= st[id].mn) st[id].mn = p;
else if(p < st[id].mn2) st[id].mn2 = p;
}
}
void bnc(int id, int l, int r){
if(l == r) return;
push_mn(lf, st[id].mx, l == md); // new value yg ke prop
push_mn(rg, st[id].mx, md+1 == r);
//cout << "here\n";
push_mx(lf, st[id].mn, l == md);
push_mx(rg, st[id].mn, md+1 == r);
}
void CHMX(int id, int l, int r, int x, int y, int p){ //a[i] = max(a[i], x);
if(r<x || y<l || p <= st[id].mn) return; // update gk ganti apa2
//cout << l << ' ' << r << ' ' << st[id].mn << ' ' << st[id].mn2 << " lr\n";
if(x<=l && r<=y && p < st[id].mn2){
push_mx(id, p, l==r);
return;
}
bnc(id, l, r);
CHMX(lf, l, md, x, y, p); CHMX(rg, md+1, r, x, y, p);
merge(id);
}
void CHMN(int id, int l, int r, int x, int y, int p){ //a[i] = min(a[i], x)
if(r<x || y<l || p >= st[id].mx) return; // update gk ganti apa2
//cout << l << ' ' << r << ' ' << st[id].mx << ' ' << st[id].mx2 << " lr\n";
if(x<=l && r<=y && p > st[id].mx2){ // mx masih ttp mx, tp ganti jadi x -> mx = x
push_mn(id, p, l==r);
return;
}
bnc(id, l, r);
CHMN(lf, l, md, x, y, p); CHMN(rg, md+1, r, x, y, p);
merge(id);
}
void que(int id, int l, int r){
if(l==r){
ans[l] = st[id].sum;
//cout << l << ' ' << ans[l] << " p\n";
return;
}
que(lf, l, md); que(rg, md+1, r);
}
} A;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
A.bd(1, 1, n);
for(int i=0; i<k; i++){
if(op[i] == 1){ // add -> a[i] = max(a[i], x);
A.CHMX(1, 1, n, left[i]+1, right[i]+1, height[i]);
} else { // remove -> a[i] = min(a[i], x)
A.CHMN(1, 1, n, left[i]+1, right[i]+1, height[i]);
}
}
A.que(1, 1, n);
for(int i=1; i<=n; i++) finalHeight[i-1] = ans[i];
return;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
98 ms |
15944 KB |
Output is correct |
| 3 |
Incorrect |
54 ms |
11604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2504 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
