Submission #1197183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197183		therickyzhang	Wall (IOI14_wall)	C++20	100 / 100	695 ms	89240 KiB

wall

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

typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second

const int INF = 1e8;

int N;
vector<pair<int,int>> tree;

pair<int,int> merge(pair<int,int> &a, pair<int,int> b) {
    if (b.F > a.S) return a = {b.F, b.F};
    if (b.S < a.F) return a = {b.S, b.S};
    return a = {max(a.F, b.F), min(a.S, b.S)};
}

void pushdown(int tl, int tr, int i) {
    if (tl != tr) {
        merge(tree[i*2], tree[i]);
        merge(tree[i*2+1], tree[i]);
        tree[i] = {0, INF};
    }
}

void update(pair<int,int> v, int l, int r, int tl = 0, int tr = N-1, int i = 1) {
    pushdown(tl, tr, i);
    if (l > r) return;
    if (tl == l && tr == r) {
        merge(tree[i], v);
        pushdown(tl, tr, i);
        return;
    }
    int tm = (tl + tr) / 2;
    update(v, l, min(r, tm), tl, tm, i * 2);
    update(v, max(l, tm + 1), r, tm + 1, tr, i * 2 + 1);
}

int query(int p, int tl = 0, int tr = N-1, int i = 1) {
    pushdown(tl, tr, i);
    if (tl == tr) return tree[i].F;
    int tm = (tl + tr) / 2;
    if (p <= tm) return query(p, tl, tm, i * 2);
    else return query(p, tm + 1, tr, i * 2 + 1);
}


void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
    ::N = N;
    tree.resize(4*N, {0, INF});
    for(int i = 0; i < K; i++) {
        if (op[i] == 1) update({height[i], INF}, left[i], right[i]);
        if (op[i] == 2) update({0, height[i]}, left[i], right[i]);

    }
    for(int i = 0; i < N; i++) {
        finalHeight[i] = query(i);
    }
}

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