| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 949987 | VinhLuu | Wall (IOI14_wall) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "wall.h"
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e6 + 5;
const ll oo = 1e9;
const int K = 5e5;
const int mod = 998244353;
//const int base = 23;
int n, k;
struct ST{
int mi[K << 1], mx[K << 1];
void pre(){
for(int i = 1; i <= 2 * k; i ++) mx[i] = 0, mi[i] = oo;
}
void update(int i,int x){
i += k - 1;
if(x == -1){
mi[i] = oo;
mx[i] = 0;
}else{
mi[i] = x;
mx[i] = x;
}
while(i > 1){
i /= 2;
mi[i] = min(mi[i << 1], mi[i << 1|1]);
mx[i] = max(mx[i << 1], mx[i << 1|1]);
}
}
int Max(int l,int r){
r++;
int ret = 0;
for(l += k - 1, r += k - 1; l < r; l /= 2, r /= 2){
if(l & 1) ret = max(ret, mx[l ++]);
if(r & 1) ret = max(ret, mx[-- r]);
}
return ret;
}
int Min(int l,int r){
r++;
int ret = oo;
for(l += k - 1, r += k - 1; l < r; l /= 2, r /= 2){
if(l & 1) ret = max(ret, mi[l ++]);
if(r & 1) ret = max(ret, mi[-- r]);
}
return ret;
}
} add, rm;
vector<pii> open[N], close[N];
void buildWall(int _n,int _k, int *op, int *left, int *right, int *height, int &finalHeight[]){
n = _n;
k = _k;
for(int i = 0; i < k; i ++){
left[i]++;
right[i]++;
if(op[i] == 1){
open[left[i]].pb({1, height[i]});
close[right[i] + 1].pb({0, i});
}else{
open[left[i]].pb({1, height[i]});
close[right[i] + 1].pb({1, i});
}
}
add.pre();
rm.pre();
set<int, greater<int>> s;
for(int i = 1; i <= n; i ++){
for(auto [t, j] : open[i]){
if(t == 1){
add.update(j + 1, height[j]);
s.insert(j + 1);
}else rm.update(j + 1, height[j]);
}
for(auto [t, j] : close[i]){
if(t == 1){
add.update(j + 1, -1);
s.erase(j + 1);
}else rm.update(j + 1, -1);
}
int tmp = (*s.begin());
int u = min(add.Max(1, tmp), rm.Min(tmp + 1, k));
finalHeight[i - 1] = u;
}
}
//#define LOCAL
#ifdef LOCAL
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
}
#endif // LOCAL