제출 #315528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
315528		qpwoeirut	벽 (IOI14_wall)	C++17	32 / 100	1533 ms	98040 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int MN = 100005;

void chmn(int& a, const int b) {if (a>b) a=b;}
void chmx(int& a, const int b) {if (a<b) a=b;}

void solve_sub1(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
    fill(finalHeight, finalHeight+N, 0);

    for (int i=0; i<K; ++i) {
        for (int j=left[i]; j<=right[i]; ++j) {
            if (op[i] == 1) {
                chmx(finalHeight[j], height[i]);
            } else {
                chmn(finalHeight[j], height[i]);
            }
        }
    }
}

multiset<int> add[MN][2], rem[MN][2];
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
    if (N <= 10000 && K <= 5000) {
        solve_sub1(N, K, op, left, right, height, finalHeight);
        return;
    }
    for (int i=0; i<K; ++i) {
        if (op[i] == 1) {
            add[left[i]][0].insert(height[i]);
            add[right[i]][1].insert(height[i]);
        } else {
            rem[left[i]][0].insert(height[i]);
            rem[right[i]][1].insert(height[i]);
        }
    }

    multiset<int> cur;
    cur.insert(0);
    for (int i=0; i<N; ++i) {
        cur.insert(add[i][0].begin(), add[i][0].end());

        finalHeight[i] = *cur.rbegin();

        for (multiset<int>::iterator it=add[i][1].begin(); it!=add[i][1].end(); ++it) {
            cur.erase(cur.find(*it));
        }
    }
    //for (int i=0; i<N; ++i) cerr << finalHeight[i] << ' '; cerr << endl;

    assert(cur.size() == 1 && *cur.begin() == 0);
    cur.clear();
    cur.insert(1001001001);
    for (int i=0; i<N; ++i) {
        cur.insert(rem[i][0].begin(), rem[i][0].end());

        chmn(finalHeight[i], *cur.begin());

        for (multiset<int>::iterator it=rem[i][1].begin(); it!=rem[i][1].end(); ++it) {
            cur.erase(cur.find(*it));
        }
    }
}

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