Submission #315526

#	Time	Username	Problem	Language	Result	Execution time	Memory
315526		qpwoeirut	Wall (IOI14_wall)	C++17	24 / 100	1469 ms	97812 KiB

wall

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

using namespace std;

const int MN = 100005;

multiset<int> add[MN][2], rem[MN][2];
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
    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());

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

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

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