제출 #727187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727187		hoainiem	Wall (IOI14_wall)	C++14	100 / 100	793 ms	186184 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define lc id<<1
#define rc id<<1^1
#define nmax 2000008
const int inf = 1e6;
using namespace std;
typedef pair<int, int> pii;
pii operator+(pii x, int y){
    return (x.fi < y) ? make_pair(y, x.fi) : ((x.fi > y && y > x.se) ? make_pair(x.fi, y) : x);
}
pii operator-(pii x, int y){
    return (x.fi > y) ? make_pair(y, x.fi) : ((x.fi < y && y < x.se) ? make_pair(x.fi, y) : x);
}
pii operator+(pii x, pii y){
    return (x + y.fi) + y.se;
}
pii operator-(pii x, pii y){
    return (x - y.fi) - y.se;
}
int N, ans[nmax];
struct segmenttrebeats{
    pii mi[nmax << 2], ma[nmax << 2];
    int lazi[nmax << 2];
    void build(int id = 1, int l = 0, int r = N - 1){
        lazi[id] = -1;
        if (l == r){
            mi[id] = {0, inf};
            ma[id] = {0, -inf};
            return;
        }
        int mid = (l + r) >> 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        mi[id] = mi[lc] - mi[rc];
        ma[id] = ma[lc] + ma[rc];
    }
    void down(int id){
        mi[lc] = mi[rc] = {lazi[id], inf};
        ma[lc] = ma[rc] = {lazi[id], -inf};
        lazi[lc] = lazi[rc] = lazi[id];
        lazi[id] = -1;
        return;
    }
    void upd_max(int u, int v, int k, int id = 1, int l = 0, int r = N - 1){
        if (r < u || l > v || mi[id].fi >= k)
            return;
        if ((u <= l && r <= v) && (ma[id].fi <= k || mi[id].se == inf)){
            mi[id] = {k, inf};
            ma[id] = {k, -inf};
            lazi[id] = k;
            return;
        }
        int mid = (l + r) >> 1;
        if (lazi[id] != -1)
            down(id);
        upd_max(u, v, k, lc, l, mid);
        upd_max(u, v, k, rc, mid + 1, r);
        mi[id] = mi[lc] - mi[rc];
        ma[id] = ma[lc] + ma[rc];
    }
    void upd_min(int u, int v, int k, int id = 1, int l = 0, int r = N - 1){
        if (r < u || l > v || k >= ma[id].fi)
            return;
        if ((u <= l && r <= v) && (mi[id].fi >= k || ma[id].se == -inf)){
            mi[id] = {k, inf};
            ma[id] = {k, -inf};
            lazi[id] = k;
            return;
        }
        int mid = (l + r) >> 1;
        if (lazi[id] != -1)
            down(id);
        upd_min(u, v, k, lc, l, mid);
        upd_min(u, v, k, rc, mid + 1, r);
        mi[id] = mi[lc] - mi[rc];
        ma[id] = ma[lc] + ma[rc];
    }
    void dfs(int id = 1, int l = 0, int r = N - 1){
        if (l == r){
            ans[l] = mi[id].fi;
            return;
        }
        int mid = (l + r) >> 1;
        if (lazi[id] != -1)
            down(id);
        dfs(lc, l, mid);
        dfs(rc, mid + 1, r);
    }
}tree;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    N = n;
    tree.build();
    for (int i = 0; i < k; i++){
        if (op[i] == 1)
            tree.upd_max(left[i], right[i], height[i]);
        else
            tree.upd_min(left[i], right[i], height[i]);
    }
    tree.dfs();
    for (int i = 0; i < n; i++)
        finalHeight[i] = ans[i];
}

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