Submission #381222

#	Time	Username	Problem	Language	Result	Execution time	Memory
381222		JerryLiu06	Wall (IOI14_wall)	C++11	100 / 100	1689 ms	130924 KiB

wall

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int, pair<int, int>> pii;

#define f first
#define s second

pii tree[8000010]; const int INF = 2e9;

bool ckmin(int& A, int B) { return (B < A) ? A = B, true : false; }
bool ckmax(int& A, int B) { return (B > A) ? A = B, true : false; }

void pushdown(int x, int l, int r) {
    ckmin(tree[x].f, tree[x].s.f); ckmax(tree[x].f, tree[x].s.s);
    
    if (l < r) for (int CHILD = 2 * x; CHILD <= 2 * x + 1; CHILD++) {
        ckmax(tree[CHILD].s.s, tree[x].s.s); ckmax(tree[CHILD].s.f, tree[CHILD].s.s);

        ckmin(tree[CHILD].s.f, tree[x].s.f); ckmin(tree[CHILD].s.s, tree[CHILD].s.f);
    }
    tree[x].s.f = INF; tree[x].s.s = 0;
}
void update(int x, int l, int r, int tl, int tr, int T, int H) { int mid = (l + r) / 2;
    pushdown(x, l, r); if (l > tr || r < tl) return ; if (tl <= l && r <= tr) {

        if (T == 1) { ckmax(tree[x].s.s, H); ckmax(tree[x].s.f, tree[x].s.s); }
        if (T == 2) { ckmin(tree[x].s.f, H); ckmin(tree[x].s.s, tree[x].s.f); } return ; 
    }
    update(2 * x, l, mid, tl, tr, T, H); update(2 * x + 1, mid + 1, r, tl, tr, T, H);
    
    pushdown(2 * x, l, mid); pushdown(2 * x + 1, mid + 1, r); tree[x].f = max(tree[2 * x].f, tree[2 * x + 1].f);
}
void genAns(int x, int l, int r, int finalHeight[]) { int mid = (l + r) / 2;
    pushdown(x, l, r); if (l == r) { finalHeight[l - 1] = tree[x].f; return ; }

    genAns(2 * x, l, mid, finalHeight); genAns(2 * x + 1, mid + 1, r, finalHeight);
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for (int i = 1; i <= 4 * N; i++) { tree[i].s.f = INF; tree[i].s.s = 0; }
    
    for (int i = 0; i < K; i++) update(1, 1, N, left[i] + 1, right[i] + 1, op[i], height[i]);

    genAns(1, 1, N, finalHeight);
}

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