Submission #770980

#	Time	Username	Problem	Language	Result	Execution time	Memory
770980		loctildore	Wall (IOI14_wall)	C++14	100 / 100	620 ms	232384 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
// trans rights
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)

int arr[2000069];

void merge(pair<int, int> &x, pair<int, int> y) {
    if (y.s < x.f) x = {y.s, y.s};
    else if (y.f > x.s) x = {y.f, y.f};
    else x = {max(x.f, y.f), min(x.s, y.s)};
}

struct node {
    int l, r;
    node *lft, *rht;
    pair<int, int> val;

    node(int tl, int tr): l(tl), r(tr), val({0, INT_MAX}) {
        if (l + 1 == r) {
            lft = rht = NULL;
            return;
        }
        lft = new node(l, (l + r) / 2);
        rht = new node((l + r) / 2, r);
    }

    void clean() {
        if (l + 1 == r) return;
        merge(lft->val, val);
        merge(rht->val, val);
        val = {0, INT_MAX};
    }

    void upd(int tl, int tr, pair<int,int> nw) {
        if (tr <= l || r <= tl) return;
        if (tl <= l && r <= tr) {
            merge(val, nw);
            return;
        }
        clean();
        lft->upd(tl, tr, nw);
        rht->upd(tl, tr, nw);
    }

    void outp() {
        if (l + 1 == r) {
            arr[l] = val.f;
            return;
        }
        clean();
        lft->outp();
        rht->outp();
    }
} *root;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    root = new node(0, n);
    for (int i = 0; i < k; i++) {
        pair<int,int> tmp = {0, INT_MAX};
        if (op[i] == 1) tmp.f = height[i];
        else tmp.s = height[i];
        root->upd(left[i], right[i] + 1, tmp);
    }
    root->outp();
    for (int i = 0; i < n; i++) {
        finalHeight[i] = arr[i];
    }
}

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