Submission #729754

#	Time	Username	Problem	Language	Result	Execution time	Memory
729754		becaido	Wall (IOI14_wall)	C++17	100 / 100	520 ms	83604 KiB

wall

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

#define lpos pos<<1
#define rpos pos<<1|1

const int SIZE = 2e6 + 5;
const int INF = (1ll << 31) - 1;

int mx[3 * SIZE], mn[3 * SIZE];

void add (int pos, int x) {
    if (mx[pos] == -1)
        mn[pos] = max (mn[pos], x);
    else if (x >= mx[pos])
        mn[pos] = x, mx[pos] = -1;
    else if (x >= mn[pos])
        mn[pos] = x;
}

void del (int pos, int x) {
    if (mx[pos] == -1)
        mn[pos] = min (mn[pos], x);
    else if (x <= mn[pos])
        mn[pos] = x, mx[pos] = -1;
    else if (x <= mx[pos])
        mx[pos] = x;
}

void push_down (int pos) {
    if (mx[pos] == -1) {
        mx[lpos] = mx[rpos] = -1;
        mn[lpos] = mn[rpos] = mn[pos];
        mx[pos] = INF, mn[pos] = 0;
    } else {
        if (mn[pos] != 0) {
            add (lpos, mn[pos]);
            add (rpos, mn[pos]);
        }
        if (mx[pos] != INF) {
            del (lpos, mx[pos]);
            del (rpos, mx[pos]);
        }
        mx[pos] = INF, mn[pos] = 0;
    }
}

void modify (int pos, int l, int r, int L, int R, int t, int h) {
    if (l == L && r == R) {
        if (t == 1)
            add (pos, h);
        else
            del (pos, h);
    } else {
        push_down (pos);
        int mid = (L + R) / 2;
        if (r <= mid)
            modify (lpos, l, r, L, mid, t, h);
        else if (l > mid)
            modify (rpos, l, r, mid + 1, R, t, h);
        else {
            modify (lpos, l, mid, L, mid, t, h);
            modify (rpos, mid + 1, r, mid + 1, R, t, h);
        }
    }
}

void dfs (int pos, int l, int r, int ans[]) {
    if (l == r)
        ans[l] = mn[pos];
    else {
        push_down (pos);
        int mid = (l + r) / 2;
        dfs (lpos, l, mid, ans);
        dfs (rpos, mid + 1, r, ans);
    }
}

void buildWall (int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
    fill (mx, mx + 3 * n + 1, INF);
    fill (mn, mn + 3 * n + 1, 0);
    for (int i = 0; i < k; i++)
        modify (1, l[i], r[i], 0, n - 1, op[i], h[i]);
    dfs (1, 0, n - 1, ans);
}

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