Submission #646119

#	Time	Username	Problem	Language	Result	Execution time	Memory
646119		NintsiChkhaidze	Radio Towers (IOI22_towers)	C++17	11 / 100	4075 ms	4828 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
#define pb push_back
#define left (h<<1),l ,(l+r)>>1
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;

const int N = 100005;
int n,a[N],l,r,d,L[N],R[N],t[4*N];
deque <int> dq;

void find(){
  /*
  while(dq.size()) dq.pop_front();
  
  for (int i =l; i <= r; i++){
    L[i] = l;
    while (dq.size() && a[dq.back()] < a[i] + d) dq.pop_back();
    if (dq.size()) L[i] = dq.back();
    dq.push_back(i);
  }

  while(dq.size()) dq.pop_front();
  for (int i = r; i >= l; i--){
    R[i] = r;
    while (dq.size() && a[dq.back()] < a[i] + d) dq.pop_back();
    if (dq.size()) R[i] = dq.back();
    dq.push_back(i);
  }*/

  for (int i = l; i <= r; i++){
    L[i] = l,R[i] = r;
    for (int j = i; j >= l; j--){
      if (a[j] >= a[i] + d) {
        L[i] = j;
        break;
      }
    }

    for (int j = i; j <= r; j++){
      if (a[j] >= a[i] + d){
        R[i] = j;
        break;
      }
    }
  }
  
}

void build(int h,int l,int r){
  if (l== r){
    t[h]=a[l];
    return;
  }
  build(left);
  build(right);
  t[h] = min(t[h*2],t[h*2+1]);
}

int getmin(int h,int l,int r,int L,int R){
  if (r < L || R < l) return 1e9;
  if (L <= l && r <= R) return t[h];
  return min(getmin(left,L,R),getmin(right,L,R));
}
void init(int N, vector<int> H) {
  n = N;
  for (int i = 1; i <= n; i++)
    a[i] = H[i-1];
  build(1,1,n);
}

int max_towers(int lf, int rg, int D) {
  l=lf+1,r=rg+1,d=D;
  find();
  vector <pair<int,int> > vec; vec.clear();
  for (int i = l; i <= r; i++)
    vec.pb({a[i],i});
  
  sort(vec.begin(),vec.end());
  int ans=0;
  for (auto [x,id]: vec){
    if (getmin(1,1,n, L[id], R[id]) < x) continue;
    ans++;
  }
  return ans;
}

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