제출 #1067433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1067433		DeathIsAwe	벽 (IOI14_wall)	C++14	100 / 100	695 ms	73732 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
pair<int,int> lazy[4194304];
bool lazyorder[4194304];


void composeadd(int action, int cur) {
    if (lazyorder[cur]) {
        if (action > lazy[cur].second) {
            lazyorder[cur] = false;
            lazy[cur].first = action;
        } else {
            lazy[cur].first = max(lazy[cur].first, action);
        }
    } else {
        lazy[cur].first = max(lazy[cur].first, action);
    }
}


void composeremove(int action, int cur) {
    if (lazyorder[cur]) {
        lazy[cur].second = min(lazy[cur].second, action);
    } else {
        if (action < lazy[cur].first) {
            lazyorder[cur] = true;
            lazy[cur].second = action;
        } else {
            lazy[cur].second = min(lazy[cur].second, action);
        }
    }
}


void compose(pair<int,int> action, bool actionorder, int cur) {
    if (actionorder) {
        composeadd(action.first, cur); composeremove(action.second, cur);
    } else {
        composeremove(action.second, cur); composeadd(action.first, cur);
    }
}


void update(int cur, int mini, int maxi, int a, int b, bool order, pair<int,int> action) {
    int dummy;
    if (mini == a && maxi == b) {
        compose(action, order, cur);
    } else if (mini <= a && maxi >= b) {
        compose(lazy[cur], lazyorder[cur], cur * 2);
        compose(lazy[cur], lazyorder[cur], cur * 2 + 1);
        lazy[cur].first = 0; lazy[cur].second = 100000;
        dummy = (mini + maxi) / 2;
        if (a <= (mini + maxi) / 2) {
            update(cur * 2, mini, dummy, a, min(b, dummy), order, action);
        }
        dummy++;
        if (b >= dummy) {
            update(cur * 2 + 1, dummy, maxi, max(a, dummy), b, order, action);
        }
    }
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i=0;i<4194304;i++) {
        lazy[i].first = 0; lazy[i].second = 100000;
        lazyorder[i] = true;
    }

    for (int i=0;i<k;i++) {
        if (op[i] == 1) {
            update(1, 0, 2097151, left[i], right[i], true, make_pair(height[i], 100000));
        } else {
            update(1, 0, 2097151, left[i], right[i], false, make_pair(0, height[i]));
        }
    }

    int bruh, sus, maxans, minans, pos;
    for (int i=0;i<n;i++) {
        bruh = 1048576;
        sus = i;
        maxans = 100000; minans = 0;
        pos = 1;
        while (pos < 4194304) {
            //cout << minans << ' ' << pos << ' ' << lazy[pos].first <<  ' ' << lazy[pos].second;
            //cout << ' ' << lazyorder[pos] << '\n';
            if (!lazyorder[pos]) {
                minans = max(minans, lazy[pos].first); minans = min(minans, maxans);
                maxans = min(maxans, lazy[pos].second); maxans = max(minans, maxans);
            } else {
                maxans = min(maxans, lazy[pos].second); maxans = max(minans, maxans);
                minans = max(minans, lazy[pos].first); minans = min(minans, maxans);
            }
            if (bruh > sus) {
                pos *= 2;
            } else {
                sus -= bruh;
                pos *= 2; pos++;
            }
            bruh /= 2;
        }
        finalHeight[i] = minans; //cout << minans << '\n' << '\n' << '\n';
    }
}

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