제출 #333757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333757		ijxjdjd	벽 (IOI14_wall)	C++11	61 / 100	860 ms	106220 KiB

wall

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

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;

typedef pair<int, int> pi;
typedef  pair<long, long> pl;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;


#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FR(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define RF(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)


const int MAXK = 500000;
const int MAXH = 100000;
const int MAXN = (int)(1e6);
int maxTree[4*MAXK+5];
int minTree[4*MAXK+5];
vector<int> row[MAXN+5];
void turn(int n, int tl, int tr, int v, bool add, int chg) {
    if (tl != tr) {
        int tm = (tl + tr)/2;
        if (v <= tm) {
            turn(2*n, tl, tm, v, add, chg);
        }
        else {
            turn(2*n+1, tm+1, tr, v, add, chg);
        }
        maxTree[n] = max(maxTree[2*n], maxTree[2*n+1]);
        minTree[n] = min(minTree[2*n], minTree[2*n+1]);
    }
    else {
        int i = n;
        if ((maxTree[i] != -1) || (minTree[i] != MAXH+5)) {
            maxTree[i] = -1;
            minTree[i] = MAXH+5;
        }
        else {
            if (add) {
                maxTree[i] = chg;
            }
            else {
                minTree[i] = chg;
            }
        }

    }
}
int get(int n, int tl, int tr, int ma, int mi) {
    if (tl == tr) {
        if (maxTree[n] != -1) {
            return mi;
        }
        else {
            return ma;
        }
    }
    else {
        int tm = (tl + tr)/2;
        if (max(ma, maxTree[2*n+1]) < min(mi, minTree[2*n+1])) {
            ma = max(ma, maxTree[2*n+1]);
            mi = min(mi, minTree[2*n+1]);
            return get(2*n, tl, tm, ma, mi);
        }
        else {
            return get(2*n+1, tm+1, tr, ma, mi);
        }
    }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for (int i = 0; i < 4*MAXK+5; i++) {
        maxTree[i] = -1;
        minTree[i] = MAXH+5;
    }
    FR(i, k) {
        row[left[i]].push_back(i);
        row[right[i]+1].push_back(i);
    }
    FR(i, n) {
        for (auto& p : row[i]) {
            turn(1, 0, k-1, p, (op[p] == 1), height[p]);
        }
        if (maxTree[1] < minTree[1]) {
            if (maxTree[1] == -1) {
                finalHeight[i] = 0;
            }
            else {
                finalHeight[i] = maxTree[1];
            }
        }
        else {
            finalHeight[i] = get(1, 0, k-1, -1, MAXH+5);
        }
    }
}
//int op[101];
//int l[101];
//int r[101];
//int h[101];
//int fH[101];
//int main() {
//    int n, k;
//    cin >> n >> k;
//    FR(i, k) {
//        cin >> op[i] >> l[i] >> r[i] >> h[i];
//    }
//    buildWall(n, k, op, l, r, h, fH);
//    FR(i, n) {
//        cout << fH[i] << endl;
//    }
//}

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