oj.uz

Submission #572714

# Submission time Handle Problem Language Result Execution time Memory
572714 2022-06-05T06:55:58 Z LunaMeme Wall (IOI14_wall) C++14
24 / 100
 319 ms 32524 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define FOR(i, x, y) for (int i = x; i < y ; i ++)
 
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
   
    vector<pair<int,ii>> phases;
    int num_add = 0;
    while(num_add < k && op[num_add] == 1 ){
        phases.PB(MP(left[num_add], MP(height[num_add], right[num_add])));
        num_add ++;
    }
    sort(phases.begin(), phases.end());
    int i_phase = 0;
    priority_queue<ii> ranges; // (height, right)
    vi arr(n, 0);
    FOR(i, 0, n){
        while(i_phase < num_add && i == phases[i_phase].first){
            ranges.push(phases[i_phase].second);
            i_phase ++;
        }
        while(!ranges.empty() && ranges.top().second < i){
            ranges.pop();
        }
        if (ranges.empty()) arr[i] = 0;
        else arr[i] = ranges.top().first;
    }
    phases.clear();
    FOR(i, num_add, k){
        //cout <<left[i] << ' ' << right[i]<< '\n';
        phases.PB(MP(left[i], MP(-height[i], right[i])));
    }
    sort(phases.begin(), phases.end());
    priority_queue<ii> Ranges; // (height, right)
    i_phase = 0;
    FOR(i, 0, n){
        while(i_phase < (k -num_add) && i == phases[i_phase].first){
            Ranges.push(phases[i_phase].second);
            i_phase ++;
        }
        while(!Ranges.empty() && Ranges.top().second < i){
            Ranges.pop();
        }
        if (!Ranges.empty()) arr[i] = min(arr[i], -Ranges.top().first);
    }
    FOR(i, 0, n){
        finalHeight[i] = arr[i];
        //cout << finalHeight[i] << ' ';
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 468 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 212 KB Output is correct
2 Correct 201 ms 19716 KB Output is correct
3 Correct 107 ms 13124 KB Output is correct
4 Correct 264 ms 31280 KB Output is correct
5 Correct 238 ms 32524 KB Output is correct
6 Correct 319 ms 29484 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 468 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 212 KB Output is correct
2 Incorrect 3 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -