Submission #1055982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055982		noyancanturk	Radio Towers (IOI22_towers)	C++17	41 / 100	4059 ms	2392 KiB

towers

#include "towers.h"

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

#define pb push_back

const int lim=1e5+100;

struct{
  int tree[lim];
  void update(int p,int val){
    p++;
    while(p<lim){
      tree[p]+=val;
      p+=p&-p;
    }
  }
  int query(int p){
    p++;
    int ans=0;
    while(p){
      ans+=tree[p];
      p-=p&-p;
    }
    return ans;
  }
  int query(int l,int r){
    if(r<l)return 0;
    return query(r)-query(l-1);
  }
}fw;

int n;
vector<int>h;
vector<int>peaks;

void init(int N, std::vector<int> H) {
  n=N;
  h=H;
  for(int i=1;i+1<n;i++){
    if(h[i-1]<h[i]&&h[i+1]<h[i]){
      peaks.pb(i);
      fw.update(i,1);
    }
  }
}

int max_towers(int L, int R, int D) {
  if(peaks.size()==1){
    if(L<peaks[0]&&peaks[0]<R&&D<=h[peaks[0]]-h[L]&&D<=h[peaks[0]]-h[R]){
      return 2;
    }
    return 1;
  }else if(D==1){
    return fw.query(L+1,R-1)+1;
  }else if(0&&L==0&&R==n-1){

  }
  int ty=0,dude=h[L],ans=1;
  for(int i=L+1;i<=R;i++){
    if(!ty){
      if(D<=h[i]-dude){
        dude=h[i];
        ty=1;
      }else{
        dude=min(dude,h[i]);
      }
    }else{
      if(D<=dude-h[i]){
        dude=h[i];
        ty=0;
        ans++;
      }else{
        dude=max(dude,h[i]);
      }
    }
  }
  return ans;
}

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