Submission #380976

#	Time	Username	Problem	Language	Result	Execution time	Memory
380976		JerryLiu06	Wall (IOI14_wall)	C++11	24 / 100	1106 ms	17388 KiB

wall

#include <bits/stdc++.h>

using namespace std;

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

#define f first
#define s second

pii tree[8000010]; const int INF = 2000000000;

void pushdown(int x, int l, int r) {
    tree[x].f.f = max(tree[x].f.f, tree[x].s.f); tree[x].f.s = max(tree[x].f.s, tree[x].s.f);
    tree[x].f.f = min(tree[x].f.f, tree[x].s.s); tree[x].f.s = min(tree[x].f.s, tree[x].s.s);

    if (l < r) { 
        tree[2 * x].s.f = max(tree[2 * x].s.f, tree[x].s.f); 
        tree[2 * x].s.s = min(tree[2 * x].s.s, tree[x].s.s);

        tree[2 * x + 1].s.f = max(tree[2 * x + 1].s.f, tree[x].s.f); 
        tree[2 * x + 1].s.s = min(tree[2 * x + 1].s.s, tree[x].s.s);
    }
    tree[x].s.f = 0; tree[x].s.s = INF;
}
void update(int x, int l, int r, int tl, int tr, int T, int val) { int mid = (l + r) / 2;
    pushdown(x, l, r); if (l > tr || r < tl) return ;

    if (T == 1) { if (tl <= l && r <= tr) { tree[x].s.f = val; return ; } }
    if (T == 2) { if (tl <= l && r <= tr) { tree[x].s.s = val; return ; } }

    update(2 * x, l, mid, tl, tr, T, val); update(2 * x + 1, mid + 1, r, tl, tr, T, val);

    pushdown(2 * x, l, mid); pushdown(2 * x + 1, mid + 1, r);

    tree[x].f.f = max(tree[2 * x].f.f, tree[2 * x + 1].f.f);
    tree[x].f.s = min(tree[2 * x].f.s, tree[2 * x + 1].f.s);
}
int query(int x, int l, int r, int pos) { int mid = (l + r) / 2;
    pushdown(x, l, r); if (r < pos || l > pos) return 0; if (l == r) return tree[x].f.f;

    return max(query(2 * x, l, mid, pos), query(2 * x + 1, mid + 1, r, pos));
}
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 = 0; tree[i].s.s = INF; }

    for (int i = 0; i < K; i++) update(1, 1, N, left[i] + 1, right[i] + 1, op[i], height[i]);
    
    for (int i = 0; i < N; i++) finalHeight[i] = query(1, 1, N, i + 1);
}

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