Submission #1039846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039846		Thunnus	Wall (IOI14_wall)	C++17	100 / 100	507 ms	111168 KiB

wall

#include <bits/stdc++.h> 
#include "wall.h"
using  namespace std;
typedef  long long ll;
typedef  pair<int, int> pp;
#define  rep(i,l,r) for(int i = (l); i < r; i++)
#define  per(i,r,l) for(int i = (r); i >= l; i--)
#define  all(x) x.begin(), x.end()
#define  sz(x) (int)(x).size()
#define  pb push_back
#define  ff first
#define  ss second 
 
const ll mod = 998244353, maxn = 2e6 + 5, inf = 1e9 + 5;

int mi[maxn << 2], mx[maxn << 2], n, res[maxn];
pp lazy[maxn << 2];

void pull_add(int x, int k){
    mi[x] = max(mi[x], k);
    mx[x] = max(mx[x], k);
    lazy[x].ff = max(lazy[x].ff, k);
    lazy[x].ss = max(lazy[x].ss, k);
}

void pull_dec(int x, int k){
    mi[x] = min(mi[x], k);
    mx[x] = min(mx[x], k);
    lazy[x].ff = min(lazy[x].ff, k);
    lazy[x].ss = min(lazy[x].ss, k);
}

void shift(int x){
    if(lazy[x].ff != -inf){
        pull_add(x << 1, lazy[x].ff);
        pull_add(x << 1 | 1, lazy[x].ff);
    }
    if(lazy[x].ss != inf){
        pull_dec(x << 1, lazy[x].ss);
        pull_dec(x << 1 | 1, lazy[x].ss);
    }
    lazy[x] = {-inf, inf};
}

void upd(int l, int r, int k, int t, int x = 1, int lx = 0, int rx = n){
    if(l <= lx && r >= rx){ // t == 1 -> set_min, else -> set_max
        if(t == 1){
            pull_add(x, k);
        }else{
            pull_dec(x, k);
        }
        return;
    } if(l >= rx || r <= lx) return;
    shift(x);
    int mid = (lx + rx) >> 1;
    upd(l, r, k, t, x << 1, lx, mid);
    upd(l, r, k, t, x << 1 | 1, mid, rx);
    mi[x] = min(mi[x << 1], mi[x << 1 | 1]);
    mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}

void get(int x = 1, int lx = 0, int rx = n){
    if(lx + 1 == rx){
        res[lx] = mi[x];
        return;
    }
    shift(x);
    int mid = (lx + rx) >> 1;
    get(x << 1, lx, mid);
    get(x << 1 | 1, mid, rx);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	::n = n;
    rep(i,0,k) upd(left[i], right[i] + 1, height[i], op[i]);
    get();
    rep(i,0,n) finalHeight[i] = res[i];
}

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