Submission #1006643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006643		The_Samurai	Wall (IOI14_wall)	C++17	100 / 100	643 ms	59332 KiB

wall

#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
const int inf = 2e9;

vector<int> mn, mx;
int sz;

// first mx, then mn

void impact(int x, int op, int v) {
    if (op == 1) {
        mx[x] = max(mx[x], v);
        if (mn[x] < v) {
            if (2 * x + 2 < mn.size()) {
                impact(2 * x + 1, 2, mn[x]);
                impact(2 * x + 2, 2, mn[x]);
            }
            mn[x] = inf;
        }
    } else {
        mn[x] = min(mn[x], v);
        if (mx[x] >= mn[x]) {
            mx[x] = mn[x];
        }
    }
}

void propagate(int x) {
    if (mx[x] != 0) {
        impact(2 * x + 1, 1, mx[x]);
        impact(2 * x + 2, 1, mx[x]);
        mx[x] = 0;
    }
    if (mn[x] != inf) {
        impact(2 * x + 1, 2, mn[x]);
        impact(2 * x + 2, 2, mn[x]);
        mn[x] = inf;
    }
}

void upd(int l, int r, int op, int v, int x, int lx, int rx) {
    if (l >= rx or lx >= r) return;
    if (l <= lx and rx <= r) {
        impact(x, op, v);
        return;
    }
    propagate(x);
    int mid = (lx + rx) >> 1;
    upd(l, r, op, v, 2 * x + 1, lx, mid);
    upd(l, r, op, v, 2 * x + 2, mid, rx);
}

int get(int i, int x, int lx, int rx) {
    // cout << lx << ' ' << rx << ' ' << mx[x] << ' ' << mn[x] << endl;
    if (rx - lx == 1) {
        return min(mx[x], mn[x]);
    }
    propagate(x);
    int mid = (lx + rx) >> 1;
    if (i < mid) return get(i, 2 * x + 1, lx, mid);
    return get(i, 2 * x + 2, mid, rx);
}

void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[]) {
    sz = 1;
    while (sz < n) sz *= 2;
    mn.assign(2 * sz - 1, inf); mx.assign(2 * sz - 1, 0);
    vector<int> brute_ans(n);
    for (int i = 0; i < q; i++) {
        upd(left[i], right[i] + 1, op[i], height[i], 0, 0, sz);
#ifdef sunnatov
        for (int j = left[i]; j <= right[i]; j++) {
            if (op[i] == 1) brute_ans[j] = max(brute_ans[j], height[i]);
            else brute_ans[j] = min(brute_ans[j], height[i]);
        }
        // for (int j = 0; j < n; j++) {
        //     finalHeight[j] = get(j, 0, 0, sz);
        //     if (finalHeight[j] != brute_ans[j]) {
        //         cout << j << ' ' << brute_ans[j] << ' ' << finalHeight[j] << endl;
        //     }
        //     assert(finalHeight[j] == brute_ans[j]);
        // }
#endif
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = get(i, 0, 0, sz);
#ifdef sunnatov
        if (finalHeight[i] != brute_ans[i]) {
            cout << i << ' ' << brute_ans[i] << ' ' << finalHeight[i] << endl;
        }
        assert(finalHeight[i] == brute_ans[i]);
#endif
    }
}

Compilation message (stderr)

wall.cpp: In function 'void impact(int, int, int)':
wall.cpp:15:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |             if (2 * x + 2 < mn.size()) {
      |                 ~~~~~~~~~~^~~~~~~~~~~

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