Submission #1144883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144883		akamizane	Wall (IOI14_wall)	C++20	100 / 100	591 ms	59656 KiB

wall

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e6 + 5; 
 
struct Node{
  int mi = 0, mx = 1e9;
};

Node t[4 * maxn];

void apply (int id, int mi, int mx){
    if (0 <= id && id < 4 * maxn){
        t[id].mi = max(t[id].mi, mi);
        t[id].mx = min(t[id].mx, mx);
        t[id].mi = min(t[id].mi, mx);
        t[id].mx = max(t[id].mx, mi);
    }
}

void update(int id, int l, int r, int u, int v, int mode, int val){
    if (r < u || v < l) return;
    if (u <= l && r <= v){
        if (mode){
            t[id].mx = min(t[id].mx, val);
            t[id].mi = min(t[id].mi, val);
        }
        else{
            t[id].mx = max(t[id].mx, val);
            t[id].mi = max(t[id].mi, val);
        }
        return;
    }
    apply(id << 1, t[id].mi, t[id].mx);
    apply(id << 1 | 1, t[id].mi, t[id].mx);
    int mid = (l + r) / 2;
    t[id] = {0, (int)1e9};
    update(id << 1, l, mid, u, v, mode, val);
    update(id << 1 | 1, mid + 1, r, u, v, mode, val);
}

int get(int id, int l, int r, int idx){
    if (l == r){
        return min(t[id].mi, t[id].mx);
    }
    int mid = (l + r) / 2;
    apply(id << 1, t[id].mi, t[id].mx);
    apply(id << 1 | 1, t[id].mi, t[id].mx);
    if(idx <= mid) return get(id << 1, l, mid, idx);
    return get(id << 1 | 1, mid + 1, r, idx);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[],
               int final_height[]) {
    for (int i = 0; i < k; i++) {
        update(1, 0, n - 1, left[i], right[i], op[i] - 1, height[i]);
    }
    for (int i = 0; i < n; i++) final_height[i] = get(1, 0, n - 1, i);
}

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