oj.uz

Submission #1062764

# Submission time Handle Problem Language Result Execution time Memory
1062764 2024-08-17T10:32:47 Z anango Wall (IOI14_wall) C++17
24 / 100
 1787 ms 169416 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 6 ms 2036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 440 KB Output is correct
2 Correct 1063 ms 169416 KB Output is correct
3 Correct 584 ms 61988 KB Output is correct
4 Correct 1787 ms 149232 KB Output is correct
5 Correct 779 ms 129620 KB Output is correct
6 Correct 718 ms 128664 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 10 ms 1916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 6 ms 2068 KB Output isn't correct
3 Halted 0 ms 0 KB -