Submission #1091605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091605		vladilius	Wall (IOI14_wall)	C++17	100 / 100	953 ms	99408 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 1e5;

vector<pii> t;

void ap1(int v, int& x){
    t[v].ff = max(t[v].ff, x);
    if (t[v].ff > t[v].ss) t[v].ss = t[v].ff;
}

void ap2(int v, int& x){
    t[v].ss = min(t[v].ss, x);
    if (t[v].ff > t[v].ss) t[v].ff = t[v].ss;
}

void push(int& v){
    int vv = 2 * v;
    ap1(vv, t[v].ff);
    ap1(vv + 1, t[v].ff);
    ap2(vv, t[v].ss);
    ap2(vv + 1, t[v].ss);
    t[v] = {0, inf};
}

void chmax(int v, int tl, int tr, int& l, int& r, int& x){
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r){
        ap1(v, x);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    push(v);
    chmax(vv, tl, tm, l, r, x);
    chmax(vv + 1, tm + 1, tr, l, r, x);
}

void chmin(int v, int tl, int tr, int& l, int& r, int& x){
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r){
        ap2(v, x);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    push(v);
    chmin(vv, tl, tm, l, r, x);
    chmin(vv + 1, tm + 1, tr, l, r, x);
}

int f(int x, pii& d){
    return min(max(x, d.ff), d.ss);
}

void get(int v, int tl, int tr, int p, int& x){
    x = f(x, t[v]);
    if (tl == tr) return;
    int tm = (tl + tr) / 2, vv = 2 * v;
    push(v);
    if (p <= tm){
        get(vv, tl, tm, p, x);
    }
    else {
        get(vv + 1, tm + 1, tr, p, x);
    }
}

void buildWall(int n, int k, int type[], int l[], int r[], int h[], int H[]){
    t.assign(4 * n, {0, inf});
    for (int i = 0; i < k; i++){
        l[i]++; r[i]++;
        if (type[i] == 1){
            chmax(1, 1, n, l[i], r[i], h[i]);
        }
        else {
            chmin(1, 1, n, l[i], r[i], h[i]);
        }
    }
    
    for (int i = 0; i < n; i++) get(1, 1, n, i + 1, H[i]);
}

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