Submission #1192615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192615		hyakup	Radio Towers (IOI22_towers)	C++20	23 / 100	4075 ms	1564 KiB

towers

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

const int inf = 2e9;

vector<int> h;

void init(int n, vector<int> H) {
  h = H;
}

int max_towers(int l, int r, int d) {
  stack<int> maxi, vales;
  maxi.push(0);
  vales.push(l);
  for( int i = l + 1; i <= r; i++ ){
    while( !vales.empty() ){
      if( maxi.top() >= h[i] + d && maxi.top() >= h[vales.top()] + d ){
        vales.push(i);
        maxi.push(0);
        break;
      }
      else if( h[i] > h[vales.top()] ){
        maxi.top() = max( maxi.top(), h[i] );
        break;
      }
      else{
        int aux = max( maxi.top(), h[vales.top()] );
        maxi.pop(); vales.pop();
        if( !maxi.empty() ) maxi.top() = max( maxi.top(), aux );
        else{
          maxi.push(0);
          vales.push(i);
          break;
        }
      }
    }
  }

  return vales.size();

}

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