Submission #1062764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062764		anango	Wall (IOI14_wall)	C++17	24 / 100	1787 ms	169416 KiB

wall

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


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    vector<vector<int>> sweep; //(ID (0=max, 1=min, 2=index_max, 3=index_min), time, value, add_or_remove_tag (0=add, 1=remove))
    for (int i=0; i<k; i++) {
        sweep.push_back({left[i],op[i]-1,height[i],0});
        sweep.push_back({right[i]+1,op[i]-1,height[i],1});
        sweep.push_back({left[i],op[i]+1,i,0});
        sweep.push_back({right[i]+1,op[i]+1,i,1});
    }
    sort(sweep.begin(), sweep.end());
    int pointer = 0;
    int num_events = sweep.size();
    multiset<int> max_values;
    multiset<int> min_values;
    set<int> max_indices;
    set<int> min_indices;
    for (int i=0; i<n; i++) {
        while (pointer<num_events && sweep[pointer][0]<=i) {
            if (sweep[pointer][1]==0) {
                if (sweep[pointer][3]==0) max_values.insert(sweep[pointer][2]);
                if (sweep[pointer][3]==1) max_values.erase(max_values.find(sweep[pointer][2]));
            }
            if (sweep[pointer][1]==1) {
                if (sweep[pointer][3]==0) min_values.insert(sweep[pointer][2]);
                if (sweep[pointer][3]==1) min_values.erase(min_values.find(sweep[pointer][2]));
            }
            if (sweep[pointer][1]==2) {
                if (sweep[pointer][3]==0) max_indices.insert(sweep[pointer][2]);
                if (sweep[pointer][3]==1) max_indices.erase(max_indices.find(sweep[pointer][2]));
            }
            if (sweep[pointer][1]==3) {
                if (sweep[pointer][3]==0) min_indices.insert(sweep[pointer][2]);
                if (sweep[pointer][3]==1) min_indices.erase(min_indices.find(sweep[pointer][2]));
            }
            pointer++;
        }
        //cout << "sweeping " << i <<" " << max_values.size() <<" " << max_indices.size() << " " << min_values.size() <<" " << min_indices.size() << endl;
        int cur_height = 0;
        if (max_indices.size() && min_indices.size()) {
            if ((*max_indices.rbegin())>*(min_indices.rbegin())) {
                cur_height = min(cur_height,*(min_values.begin()));
                cur_height = max(cur_height,*(max_values.rbegin()));
            }
            else {
                cur_height = max(cur_height,*(max_values.rbegin()));
                cur_height = min(cur_height,*(min_values.begin()));
            }
            //cout << "SOLVING " << i <<" " << (*max_indices.rbegin()) <<" " << *(min_indices.rbegin()) <<" " << *(max_values.rbegin()) <<" " <<*(max_values.rbegin()) << endl; 
        }
        else if (max_indices.size()) {
            cur_height = max(cur_height,*(max_values.rbegin()));
        }
        else if (min_indices.size()) {
            cur_height = min(cur_height,*(min_values.begin()));
        }
        else {
            //cout << "BOTH EMPTY " << i << endl;
        }
        finalHeight[i] = cur_height;
    }

    return;
}

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