Submission #821456

#	Time	Username	Problem	Language	Result	Execution time	Memory
821456		eltu0815	Radio Towers (IOI22_towers)	C++17	0 / 100	741 ms	7080 KiB

towers

#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()) {
        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
*/

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23