Submission #1015601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015601		nam6	Radio Towers (IOI22_towers)	C++17	0 / 100	4061 ms	21684 KiB

towers

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

int sommet; 
vector<int> altitudes; 
vector< pair<int, int> > intervalle; 
set<int> choisis; 

const int DECA = 1<<22; 
int arbre[2*DECA]; 

void modif(int pos, int val){
  pos+=DECA; 
  arbre[pos] = val; 
  while(pos > 1){
    pos/=2; 
    arbre[pos] = max(arbre[2*pos], arbre[2*pos+1]); 
  }
}

int calcMax(int deb, int fin){
  if(deb==fin)
    return arbre[fin]; 
  if(deb%2==1)
    return max(arbre[deb], calcMax(deb+1, fin)); 
  if(fin%2==0)
    return max(calcMax(deb, fin-1), fin); 
  return calcMax(deb/2, fin/2); 
}

void init(int N, vector<int> H) {
  altitudes = H;   
}

int max_towers(int L, int R, int D) {
  for(int pos=L; pos<=R; pos++){
    intervalle.push_back({altitudes[pos],pos});
    modif(pos, altitudes[pos]);
  }
  sort(intervalle.begin(), intervalle.end()); 
  for(int i=0; i<intervalle.size(); i++){
    bool estOk = true; 
    auto igauche = choisis.lower_bound(intervalle[i].second); 
    if(igauche != choisis.begin()){
      igauche--; 
      int gauche = *igauche; 
      int maxiGauche = calcMax(gauche + DECA, intervalle[i].second+DECA); 
      if(maxiGauche - max(gauche, intervalle[i].first) < D){
        estOk = false; 
      }
    }
    
    auto idroite = choisis.upper_bound(intervalle[i].second); 
    if(idroite != choisis.end()){
      int droite = *idroite; 
      int maxiDroite = calcMax(intervalle[i].second+DECA, droite+DECA); 
      if(maxiDroite- max(droite, intervalle[i].first) < D){
        estOk = false; 
      }
    }
    if(estOk){
      choisis.insert(intervalle[i].second);
    }
  }
  return choisis.size();
}

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i=0; i<intervalle.size(); i++){
      |                ~^~~~~~~~~~~~~~~~~~

• 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