Submission #385364

#	Time	Username	Problem	Language	Result	Execution time	Memory
385364		ParsaAlizadeh	Wall (IOI14_wall)	C++17	61 / 100	534 ms	16492 KiB

wall

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

#define lc  (id << 1)
#define rc  (lc | 1)

typedef long long ll;
int const N = 1e5 + 5;

int seg[N << 2][2];

inline void apply(int mn, int mx, int res[2]) {
    for (int i : {0, 1})
        res[i] = min(mx, max(mn, res[i]));
}

inline void shift(int id) {
    apply(seg[id][0], seg[id][1], seg[lc]);
    apply(seg[id][0], seg[id][1], seg[rc]);
    seg[id][0] = 0;
    seg[id][1] = INT_MAX;
}

void build(int id, int l, int r) {
    if (r - l == 1) {
        return;
    }
    int mid = (l + r) >> 1;
    build(lc, l, mid); build(rc, mid, r);
    seg[id][1] = INT_MAX;
}

void update(int id, int l, int r, int ql, int qr, int mn, int mx) {
    if (qr <= l || r <= ql)
        return;
    if (ql <= l && r <= qr)
        return apply(mn, mx, seg[id]);
    shift(id);
    int mid = (l + r) >> 1;
    update(lc, l, mid, ql, qr, mn, mx);
    update(rc, mid, r, ql, qr, mn, mx);
}

void finish(int id, int l, int r, int arr[]) {
    if (r - l == 1) {
        arr[l] = seg[id][0];
        return;
    }
    shift(id);
    int mid = (l + r) >> 1;
    finish(lc, l, mid, arr);
    finish(rc, mid, r, arr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    build(1, 0, n);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            update(1, 0, n, left[i], right[i] + 1, height[i], INT_MAX);
        }
        else {
            update(1, 0, n, left[i], right[i] + 1, 0, height[i]);
        }
    }
    finish(1, 0, n, finalHeight);
    return;
}

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