Submission #1239079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239079		AlperenT_	Radio Towers (IOI22_towers)	C++20	14 / 100	349 ms	27052 KiB

towers

#include "towers.h"

#include <vector>
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const int maxn = 1e6 + 10 , inf = 1e9+ 10 , mod = 998244353;
int n ,d  ;
vector <int> h  ; 

struct segtree{
  int mn[4*maxn] , id[4*maxn] ;
  vector <int> a ;  
  void bui(int p = 1,  int l = 0 , int r= n){
    int mid = (l+r)/2 ,pl =p <<1,pr=p<<1|1; 
    if(l==r){
      mn[p] = a[l] ;
      id[p] = l ;
      return; 
    }
    bui(pl,l,mid);
    bui(pr,mid+1,r) ;
    mn[p] = min(mn[pl] , mn[pr]) ;
    id[p] = id[pl] ;
    if(mn[p] == mn[pr])id[p] = id[pr] ;
  }
  pii que(int le ,int ri , int p =1 , int l = 0 , int r= n){
    int mid = (l+r)/2 ,pl =p <<1,pr=p<<1|1; 
    if(le > r || l > ri)return {inf , 0 };
    if(le <= l && r <= ri)return {mn[p] , id[p]} ;
    pii a= que(le,ri,pl,l,mid) ;
    pii b = que(le,ri,pr,mid+1,r);
    pii c ;
    c.F = min(a.F ,b.F); 
    c.S = a.S ;
    if(c.F == b.F)c.S = b.S ;
    return c;
  }
};
segtree mn , mx ;
vector <pii> ans ;
vector <pair<int,pii> > ed; vector <int> az; 
int lf[maxn] ,ri[maxn] , vj[maxn] , pr[maxn] ,pr2[maxn] ,ok[maxn] , rpar[maxn] , lpar[maxn];
void bui(int l , int r){
  int m = mx.que(l , r).S ;
  az.pb(m); 
  vj[m] = 1; 
  ok[m] =1 ;
  if(m!=l){
    if(h[m]-mn.que(l,m-1).F >= d){
      int x = mx.que(l , m-1).S ;
      rpar[x] = m ;
      lpar[x] = lpar[m] ;
      bui(l , m-1) ;
      ok[m] =0 ;
      lf[m] =1 ;
    }
    
  }
  if(m!=r){
    if(h[m]-mn.que(m+1,r).F >= d){
      int x = mx.que(m+1, r).S ;
      lpar[x] = m ;
      rpar[x] = rpar[m] ;
      bui(m+1,r) ;
      ok[m] =0 ;
      ri[m] =1 ;
    }
  }
}
int mark[maxn] ;
void init(int N, std::vector<int> H) {
  n = N ; 
  h.pb(0);
  rep(i , 0 , n-1)h.pb(H[i]) ; 
  mn.a = h;
  vector <int> h2 ;
  rep(i , 0 ,n){
    h2.pb(-h[i]) ;
  }
  mx.a = h2 ;
  mn.bui();
  mx.bui();
}
bool ook =0 ;

void solve(int D){
  d = D ;
   bui(1 , n);
  sort(all(az)) ;
  rep(i ,1, n){
    pr[i] = pr[i-1] + vj[i] ;
    pr2[i] = pr2[i-1] + ok[i] ;
  }
}

int max_towers(int l, int r, int D) {
  if(ook == 0){
    solve(D);
    ook =1 ;
  }
  l++;
  r++;
  if(pr[r] - pr[l-1] <= 2)return 1;
  int x =lower_bound(all(az) , l) - az.begin() ;
  int y = lower_bound(all(az) , r+1) - az.begin() - 1 ;
  int ans = pr2[r]-pr2[l-1]; 
  x = az[x];
  y = az[y];
  if(ok[x] == 0 && ri[x] == 0 && h[rpar[x]]-h[x] >= d)ans++;
  if(ok[y]==0 && lf[y] ==0 && h[lpar[y]]-h[y] >= d)ans++;
  return  ans;
}

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