Submission #936230

#	Time	Username	Problem	Language	Result	Execution time	Memory
936230		peterandvoi	Wall (IOI14_wall)	C++17	100 / 100	663 ms	75776 KiB

wall

#include <bits/stdc++.h>

#include "wall.h"

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int INF = (int) 1e9;

struct segment_tree {
    int n;
    vector<int> add, rmv, s;

    segment_tree() {};

    segment_tree(int n): n(n) {
        add.resize(4 << __lg(n), -INF);
        rmv.resize(4 << __lg(n), INF);
        s.resize(4 << __lg(n));
    };

    void apply(int id, int x, int y) {
        s[id] = max(s[id], x);
        s[id] = min(s[id], y);
        if (y < add[id]) {
            add[id] = rmv[id] = y;
        } else if (x > rmv[id]) {
            add[id] = rmv[id] = x;
        } else {
            add[id] = max(add[id], x);
            rmv[id] = min(rmv[id], y);
        }
    }

    void push(int id) {
        if (add[id] != -INF || rmv[id] != INF) {
            apply(id << 1, add[id], rmv[id]);
            apply(id << 1 | 1, add[id], rmv[id]);
            add[id] = -INF;
            rmv[id] = INF;
        }
    }

    void upd(int id, int l, int r, int u, int v, int x, int y) {
        if (u <= l && r <= v) {
            apply(id, x, y);
            return;
        }
        push(id);
        int mid = l + r >> 1;
        if (u <= mid) {
            upd(id << 1, l, mid, u, v, x, y);
        }
        if (mid < v) {
            upd(id << 1 | 1, mid + 1, r, u, v, x, y);
        }
    }

    void upd(int l, int r, int x, int y) {
        upd(1, 0, n - 1, l, r, x, y);
    }

    int get(int i) {
        int id = 1, l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            push(id);
            id <<= 1;
            if (i <= mid) {
                r = mid;
            } else {
                l = mid + 1;
                id |= 1;
            }
        }
        return s[id];
    }
};

#ifdef ngu
const int N = (int) 1e6 + 5;

#define left phan
#define right minh

int n, k;
int op[N], left[N], right[N], height[N], finalHeight[N];
#endif

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    segment_tree st(n);
    for (int i = 0; i < k; ++i) {
        st.upd(left[i], right[i], op[i] == 1 ? height[i] : -INF, op[i] == 2 ? height[i] : INF);
    }
    for (int i = 0; i < n; ++i) {
        finalHeight[i] = st.get(i);
    }
}

#ifdef ngu
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n >> k;
    for (int i = 0; i < k; ++i) {
        cin >> op[i] >> left[i] >> right[i] >> height[i];
    }
    buildWall(n, k, op, left, right, height, finalHeight);
    for (int i = 0; i < n; ++i) {
        cout << finalHeight[i] << " ";
    }
}
#endif

Compilation message (stderr)

wall.cpp: In member function 'void segment_tree::upd(int, int, int, int, int, int, int)':
wall.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int mid = l + r >> 1;
      |                   ~~^~~
wall.cpp: In member function 'int segment_tree::get(int)':
wall.cpp:71:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |             int mid = l + r >> 1;
      |                       ~~^~~

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