Submission #30911

#	Time	Username	Problem	Language	Result	Execution time	Memory
30911		kajebiii	Wall (IOI14_wall)	C++14	100 / 100	1453 ms	205252 KiB

wall

#include "wall.h"
#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi; typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

struct NODE{
    int l, r; pi val;
    NODE *lp, *rp;

    NODE(int a, int b) : l(a), r(b), val(pi(0, 0)), lp(NULL), rp(NULL) {
        if(a == b) return;
        int m = (a+b) >> 1;
        lp = new NODE(a, m);
        rp = new NODE(m+1, b);
    }
    pi merge(pi a, pi b) {
        return pi(min(max(a.one, b.one), b.two), min(max(a.two, b.one), b.two));
    }
    void lazy() {
        if(lp) {
            lp->val = merge(lp->val, val);
            rp->val = merge(rp->val, val);
        }
    }
    void update(int a, int b, pi v) {
        if(b < l || r < a) return;
        lazy();
        if(a <= l && r <= b) {
            val = merge(val, v);
            return;
        }
        lp->update(a, b, v);
        rp->update(a, b, v);
        val = pi(min(lp->val.one, rp->val.one), max(lp->val.two, rp->val.two));
    }
    int getV(int v) {
        if(v < l || r < v) return -1;
        if(l == r) return val.one;
        lazy();
        int lv = lp->getV(v);
        int rv = rp->getV(v);
        return max(lv, rv);
    }
};

int N, Q;
void buildWall(int n, int k, int opp[], int ll[], int rr[], int hh[], int fh[]){
    N = n; Q = k;
    NODE *root = new NODE(0, N-1);
    for(int q=0; q<Q; q++) {
//        printf("%d start\n", q);
        int o = opp[q], l = ll[q], r = rr[q], h = hh[q];
        pi val = pi(-INF, +INF);
        if(o == 1) val.one = h; else val.two = h;
        root->update(l, r, val);
    }
    for(int i=0; i<N; i++) fh[i] = root->getV(i);
    return;
}

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