Submission #531114

#	Time	Username	Problem	Language	Result	Execution time	Memory
531114		buidangnguyen05	Wall (IOI14_wall)	C++14	61 / 100	457 ms	26864 KiB

wall

/* input

*/

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 10, inf = 2e9;
int ma[4 * N], mi[4 * N];

void build(int s, int l, int r) {
    ma[s] = 0; mi[s] = inf;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(s << 1, l, mid);
    build(s << 1 | 1, mid + 1, r);
}

void push(int s) {
    int par = s >> 1;
    if (mi[s] <= ma[par]) ma[s] = mi[s] = ma[par];
    else ma[s] = max(ma[s], ma[par]);
    mi[s] = min(mi[s], mi[par]);
}

void update(int s, int l, int r, int u, int v, int q, int val) {
    if (l > v || u > r) return;
    if (l >= u && r <= v) {
        if (q == 1) mi[s] = min(mi[s], val);
        else {
            if (mi[s] <= val) ma[s] = mi[s] = val;
            else ma[s] = max(ma[s], val);
        }
        return;
    }
    push(s << 1); push(s << 1 | 1);
    ma[s] = -inf; mi[s] = inf;
    int mid = (l + r) >> 1;
    update(s << 1, l, mid, u, v, q, val);
    update(s << 1 | 1, mid + 1, r, u, v, q, val);
}

int get(int s, int l, int r, int pos) {
    if (l == r) return min(ma[s], mi[s]);
    push(s << 1); push(s << 1 | 1);
    int mid = (l + r) >> 1;
    if (pos <= mid) return get(s << 1, l, mid, pos);
    return get(s << 1 | 1, mid + 1, r, pos);
}

void buildWall(int n, int m, int type[], int l[], int r[], int val[], int ans[]) {
    build(1, 1, n);

    for (int i = 0; i < m; ++i)  update(1, 1, n, l[i] + 1, r[i] + 1, type[i] - 1, val[i]);

    for (int i = 1; i <= n; ++i) ans[i - 1] = get(1, 1, n, i);
}

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