Submission #1305617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305617		Taxiradio	Radio Towers (IOI22_towers)	C++20	0 / 100	292 ms	2208 KiB

towers

#include "towers.h"
#include<bits/stdc++.h>
using namespace std;

//#define int int64_t

int M = 1000000002;

vector<int> u;

int n;

void init(int N, std::vector<int> H) {
  n = N;
  vector<int> w(N , M);
  stack<array<int , 2>> a;
  a.push({0 , M});
  for(int i = 0; i < N; i++){
    int o = 0;
    while(a.top()[0]>H[i]){
      o = max(o , a.top()[1]);
      a.pop();
    }
    a.top()[1] = max(a.top()[1] , o);
    w[i] = min(w[i] , a.top()[1]-H[i]+1);
    a.push({H[i] , H[i]});
  }
  while(!a.empty())a.pop();
  a.push({0 , M});
  for(int i = N-1; i >= 0; i--){
    int o = 0;
    while(a.top()[0]>H[i]){
      o = max(o , a.top()[1]);
      a.pop();
    }
    a.top()[1] = max(a.top()[1] , o);
    w[i] = min(w[i] , a.top()[1]-H[i]+1);
    a.push({H[i] , H[i]});
  }
  for(int i = 0; i < N; i++){
    u.push_back(w[i]);
  }
  sort(u.begin() , u.end());
}

int max_towers(int L, int R, int D) {
  return n-(upper_bound(u.begin() , u.end() , D)-u.begin());
}

• 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