Submission #949988

#	Time	Username	Problem	Language	Result	Execution time	Memory
949988		VinhLuu	Wall (IOI14_wall)	C++17	0 / 100	122 ms	204748 KiB

wall

#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

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39