Submission #646142

#	Time	Username	Problem	Language	Result	Execution time	Memory
646142		NintsiChkhaidze	Radio Towers (IOI22_towers)	C++17	23 / 100	4030 ms	9264 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
#define s second
#define f first
using namespace std;

const int N = 100005;
int n,a[N],l,r,d,L[N],R[N],t[4*N];
bool b[N];
vector <pair<pair<int,int>,int> > val;

struct {
  int maxr;
  int maxl;
} T[4*N];

void upd(int h,int l,int r,int idx){
  if (l == r){
    T[h].maxl = l;
    T[h].maxr = l;
    return;
  }

  if (idx > (l+r)/2) upd(right,idx);
  else upd(left,idx);

  //maxl
  if (b[T[h*2].maxl]) T[h].maxl = T[h*2].maxl;
  else if (b[T[h*2 + 1].maxl]) T[h].maxl = T[h*2+1].maxl;
  else T[h].maxl = 0;

  //maxr
  if (b[T[h*2+1].maxr]) T[h].maxr = T[h*2+1].maxr;
  else if (b[T[h*2].maxr]) T[h].maxr = T[h*2].maxr;
  else T[h].maxr = 0;
}

int getmaxl(int h,int l,int r,int L,int R){
  if (r < L || R < l) return 0;
  if (L <= l && r <= R) return T[h].maxl;

  int x = getmaxl(left,L,R),y = getmaxl(right,L,R);
  if (b[x]) return x;
  if (b[y]) return y;
  return 0;
}

int getmaxr(int h,int l,int r,int L,int R){
  if (r < L || R < l) return 0;
  if (L <= l && r <= R) return T[h].maxr;

  int x = getmaxr(left,L,R),y = getmaxr(right,L,R);
  if (b[y]) return y;
  if (b[x]) return x;
  return 0;
}
void find(){
  for (int i =1;i<=n;i++) 
    b[i]=0;
  
  for (int j = 0;j < val.size(); j++){
    int tp = val[j].f.s,id = val[j].s;
    if (tp == 2){
      b[id] = 1;
      upd(1,1,n,id);
    }else{
      L[id] = getmaxr(1,1,n,l,id - 1);
      R[id] = getmaxl(1,1,n,id + 1,r);
      if (!L[id]) L[id] = l;
      if (!R[id]) R[id] = r;
    }
  }

}

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;
  vector <pair<int,int> > vec; 
  vec.clear(); val.clear();
  
  for (int i = l; i <= r; i++){
    val.pb({{a[i]-d,2},i});
    val.pb({{a[i],1},i});
    vec.pb({a[i],i});
  }
  using P = pair<pair<int,int>,int> ;
  sort(val.begin(),val.end(), greater <P> ());
  sort(vec.begin(),vec.end());
  
  find();
  
  int ans=0;
  for (auto [x,id]: vec)
    if (getmin(1,1,n, L[id], R[id]) >= x) ans++;
  return ans;
}

Compilation message (stderr)

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

• 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