oj.uz

Submission #1015620

# Submission time Handle Problem Language Result Execution time Memory
1015620 2024-07-06T15:28:45 Z nam6 Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 20816 KB 
#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<<17; 
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 - intervalle[i].first < D){
        estOk = false; 
      }
    }
    
    auto idroite = choisis.lower_bound(intervalle[i].second); 
    if(idroite != choisis.end()){
      int droite = *idroite; 
      int maxiDroite = calcMax(intervalle[i].second+DECA, droite+DECA); 
      if(maxiDroite-intervalle[i].first < D){
        estOk = false; 
      }
    }
    if(estOk){
      choisis.insert(intervalle[i].second);
    }
  }
  return choisis.size();
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4026 ms 18292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '292', found: '291'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '292', found: '291'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4040 ms 20816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4029 ms 19236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '292', found: '291'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4026 ms 18292 KB Time limit exceeded
2 Halted 0 ms 0 KB -