Submission #1141684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141684		Issa	Radio Towers (IOI22_towers)	C++17	17 / 100	272 ms	2776 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e6 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e9 + 100;
const ll MOD = 998244353;
const int maxl = 20;
const ll P = 31;

int n;
int a[maxn];
int l[maxn];
int r[maxn];
int f[maxn];

void init(int N, std::vector<int> H) {
    n = N;
    for(int i = 1; i <= n; i++){
        a[i] = H[i-1];
    } vector<int> v;
    for(int i = 1; i <= n; i++){
        while(v.size() && a[v.back()] > a[i]){
            l[i] = max({l[i], l[v.back()], a[v.back()]});
            v.pop_back();
        } if(v.empty()) l[i] = inf * 2;
        v.push_back(i);
    } v.clear();
    for(int i = n; i > 0; i--){
        while(v.size() && a[v.back()] > a[i]){
            r[i] = max({r[i], r[v.back()], a[v.back()]});
            v.pop_back();
        } if(v.empty()) r[i] = inf * 2;
        v.push_back(i);
        f[i] = min(l[i], r[i]) - a[i];
    } sort(f + 1, f + n + 1, greater<int>());
}

int max_towers(int L, int R, int D) {
    L++; R++;
    int ans = 1;
    for(int l = 2, r = n; l <= r; ){
        int mid = (l + r) >> 1;
        if(f[mid] < D) r = mid - 1;
        else l = mid + 1, ans = mid;
    } return ans;
}

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