제출 #30910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30910		kajebiii	벽 (IOI14_wall)	C++14	100 / 100	1606 ms	205248 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);
    }
    void lazy() {
        if(lp) {
            lp->val.one = max(lp->val.one, val.one);
            lp->val.two = max(lp->val.two, val.one);
            lp->val.one = min(lp->val.one, val.two);
            lp->val.two = min(lp->val.two, val.two);

            rp->val.one = max(rp->val.one, val.one);
            rp->val.two = max(rp->val.two, val.one);
            rp->val.one = min(rp->val.one, val.two);
            rp->val.two = min(rp->val.two, val.two);
        }
    }
    void update(int a, int b, pi v) {
        if(b < l || r < a) return;
        lazy();
        if(a <= l && r <= b) {
            if(v.one == -INF) {
                val.one = min(val.one, v.two);
                val.two = min(val.two, v.two);
            }else if(v.two == INF) {
                val.one = max(val.one, v.one);
                val.two = max(val.two, v.one);
            }
            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