Submission #831336

#	Time	Username	Problem	Language	Result	Execution time	Memory
831336		chanhchuong123	Wall (IOI14_wall)	C++14	100 / 100	508 ms	69524 KiB

wall

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

const int INF = 1e9 + 7;
const int MAX = 2000020;
int n, k;
pair<int, int> st[(1 << 22) + 5];

void build(int id, int l, int r) {
    st[id] = make_pair(+INF, -INF);
    if (l == r) {
        st[id] = make_pair(+INF, 0);
        return;
    }
    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}

void pushMax(int id, int h) {
    st[id].first = max(st[id].first, h); st[id].second = max(st[id].second, h);
}
void pushMin(int id, int h) {
    st[id].first = min(st[id].first, h); st[id].second = min(st[id].second, h);
}
void push(int id) {
    if (st[id].first != +INF) {
        pushMin(id << 1, st[id].first);
        pushMin(id << 1 | 1, st[id].first);
    }
    if (st[id].second != -INF) {
        pushMax(id << 1, st[id].second);
        pushMax(id << 1 | 1, st[id].second);
    }
    st[id] = make_pair(+INF, -INF);
}

void update(int id, int l, int r, int u, int v, int h, int t) {
    if (l > v || r < u) return;
    if (l >= u && r <= v) {
        if (!t) pushMax(id, h);
        else pushMin(id, h);
        return;
    }
    push(id);
    int mid = l + r >> 1;
    update(id << 1, l, mid, u, v, h, t);
    update(id << 1 | 1, mid + 1, r, u, v, h, t);
}

void getAns(int id, int l, int r, int ans[]) {
    if (l == r) ans[l] = st[id].second;
    else {
        push(id);
        int mid = l + r >> 1;
        getAns(id << 1, l, mid, ans);
        getAns(id << 1 | 1, mid + 1, r, ans);
    }
}

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
    n = N, k = K;
    build(1, 0, n - 1);
    for (int i = 0; i < k; ++i) {
        update(1, 0, n - 1, left[i], right[i], height[i], op[i] - 1);
    }
    getAns(1, 0, n - 1, finalHeight);
}

Compilation message (stderr)

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:16:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |     int mid = l + r >> 1;
      |               ~~^~~
wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:47:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int mid = l + r >> 1;
      |               ~~^~~
wall.cpp: In function 'void getAns(int, int, int, int*)':
wall.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid = l + r >> 1;
      |                   ~~^~~

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