oj.uz

Submission #821516

# Submission time Handle Problem Language Result Execution time Memory
821516 2023-08-11T11:00:45 Z eltu0815 Radio Towers (IOI22_towers) C++17
0 / 100
 644 ms 6208 KB 
#include "towers.h"
 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

int n;
vector<int> h;
set<int> st;
priority_queue<pair<int, pii> > pq;

vector<pii> q;

void init(int N, std::vector<int> H) {
    n = N; h = H;
    st.insert(0); st.insert(N - 1);
    for(int i = 1; i < N - 1; ++i) {
        if(h[i - 1] < h[i] && h[i] > h[i + 1]) st.insert(i);
        if(h[i - 1] > h[i] && h[i] < h[i + 1]) st.insert(i);
    }
    for(auto it = st.begin(); it != st.end(); ++it) {
        if(it == st.end()) break;
        pq.push({-abs(H[*it] - H[*next(it)]), {*it, *next(it)}});
    }
    
    if(st.size() >= 2 && H[*st.begin()] >= H[*next(st.begin())]) st.erase(st.begin());
    if(st.size() >= 2 && H[*st.rbegin()] >= H[*next(st.rbegin())]) st.erase(prev(st.end()));
    
    q.push_back({0, (st.size() - 1) / 2 + 1});
    while(!pq.empty()) {
        while(!pq.empty()) {
            int i = pq.top().second.first, j = pq.top().second.second;
            if(st.find(i) == st.end() || st.find(j) == st.end()) pq.pop();
            else break;
        }
            
        int D = -pq.top().first;
        while(!pq.empty() && -pq.top().first == D) {
            int i = pq.top().second.first, j = pq.top().second.second;
            pq.pop();
            
            if(st.find(i) == st.end() || st.find(j) == st.end()) continue;
            
            st.erase(st.find(i));
            st.erase(st.find(j));
            
            if(!st.empty() && *st.begin() < i && *st.rbegin() > j) {
                int prv = *prev(st.lower_bound(i));
                int nxt = *st.lower_bound(j);
                pq.push({-abs(H[prv] - H[nxt]), {prv, nxt}});
            }
        }
        
//        cout << D << " : ";
//        for(auto it : st) cout << it << ' ';
//        cout << endl;
        
        q.push_back({D, (st.size() - 1) / 2 + 1});
    }
}

int max_towers(int l, int r, int d) {
    pii p = {d, -1};
    int i = prev(lower_bound(q.begin(), q.end(), p)) - q.begin();
    return q[i].second;
}

/*
7 3
10 20 60 40 50 30 70
1 5 10
2 2 100
0 6 17

8 4
20 10 40 30 40 20 30 10
0 6 1
0 6 10
0 6 20
0 6 30

7 3
10 30 20 30 20 30 20
0 5 1
0 5 10
0 5 20
*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 976 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 557 ms 6208 KB 1st lines differ - on the 1st token, expected: '11903', found: '33010'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 1616 KB Output is correct
2 Correct 572 ms 6152 KB Output is correct
3 Incorrect 644 ms 6208 KB 3rd lines differ - on the 1st token, expected: '5845', found: '1894'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 976 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -