Submission #498619

#	Time	Username	Problem	Language	Result	Execution time	Memory
498619		gozonite	Wall (IOI14_wall)	C++14	100 / 100	582 ms	67756 KiB

wall

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>
#include <queue>
#include <tuple>
#include <cmath>
#include <cctype>
#include <stack>
#include <cassert>
using namespace std;
using ll = long long;

int ns;
int lzMin[8000001], lzMax[8000001];
int ans[2000000];

void pushdown(int k, int l, int r) {
    if (l == r) return;
    if (lzMin[k] == -1 && lzMax[k] == 1e6) return;
    for (int j = 2*k; j <= 2*k+1; j++) {
        lzMin[j] = max(lzMin[j], lzMin[k]); lzMax[j] = max(lzMax[j], lzMin[k]);
        lzMax[j] = min(lzMax[j], lzMax[k]); lzMin[j] = min(lzMin[j], lzMax[k]);
    }
    lzMin[k] = -1; lzMax[k] = 1e6;
}
void minr(int a, int b, int v, int k = 1, int l = 0, int r = ns-1) {
    if (r < a || b < l) return;
    if (a <= l && r <= b) {
        lzMin[k] = max(lzMin[k], v);
        lzMax[k] = max(lzMax[k], v);
    } else {
        int mid = (l+r)/2;
        pushdown(k, l, r);
        minr(a, b, v, 2*k, l, mid);
        minr(a, b, v, 2*k+1, mid+1, r);
    }
}
void maxr(int a, int b, int v, int k = 1, int l = 0, int r = ns-1) {
    if (r < a || b < l) return;
    if (a <= l && r <= b) {
        lzMax[k] = min(lzMax[k], v);
        lzMin[k] = min(lzMin[k], v);
    } else {
        int mid = (l+r)/2;
        pushdown(k, l, r);
        maxr(a, b, v, 2*k, l, mid);
        maxr(a, b, v, 2*k+1, mid+1, r);
    }
}
void walk(int k = 1, int l = 0, int r = ns-1) {
    if (l == r) ans[l] = lzMin[k];
    else {
        int mid = (l+r)/2;
        pushdown(k, l, r);
        walk(2*k, l, mid);
        walk(2*k+1, mid+1, r);
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    ns = n;
    minr(0, n-1, 0); maxr(0, n-1, 0);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            minr(left[i], right[i], height[i]);
        } else {
            maxr(left[i], right[i], height[i]);
        }
    }

    walk();
    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