Submission #1079544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079544		LittleOrange	Radio Towers (IOI22_towers)	C++17	100 / 100	1646 ms	196648 KiB

towers

#include "towers.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = int;
const ll big = 1e9+10;
ll n;
ll w;
ll u;
vector<ll> h,lh,rh,hh,hs,inc,decc,hhs;
//ll mx;
vector<ll> ps;
vector<pair<ll,ll>> rgs;
struct obj{
  ll v,c;
  bool operator<(const obj &o) const{
    return v<o.v;
  }
  bool operator>(const obj &o) const{
    return v>o.v;
  }
};
struct dat{
  ll c,l,r;
  dat():c(0),l(big),r(-big){}
  dat(ll x, ll y, ll z):c(x),l(y),r(z){}
  void put(ll i){
    c = 1;
    l = i;
    r = i;
  }
  dat operator+(const dat &o) const{
    return dat(c+o.c,min(l,o.l),max(r,o.r));
  }
};
struct node{
  ll l,r,m;
  dat v;
  node *L,*R;
  node(ll a, ll b):l(a),r(b),m(a+b>>1),v(),L(nullptr),R(nullptr){
    if(a<b){
      L = new node(l,m);
      R = new node(m+1,r);
    }
  }
  void put(ll i){
    if (l==r) v.put(i);
    else{
      if (i<=m) (L=new node(*L))->put(i);
      else (R=new node(*R))->put(i);
      v = L->v+R->v;
    }
  }
  dat qry(ll ql, ll qr){
    //cerr << "qry " << ql << " " << qr << " " << l << " " << r << " " << v.l << " " << v.r << " " << v.c << "\n"; 
    if (ql<=l&&r<=qr) return v;
    else{
      if (qr<=m) return L->qry(ql,qr);
      else if (ql>m) return R->qry(ql,qr);
      else return L->qry(ql,qr)+R->qry(ql,qr);
    }
  }
};
struct segtree{
  vector<node*> rt;
  segtree(){}
  segtree(ll n){
    rt.push_back(new node(0,n-1));
  }
  void nw(){
    rt.push_back(new node(*rt.back()));
  }
  void put(ll t, ll i){
    rt[t]->put(i);
  }
  dat qry(ll t, ll ql, ll qr){
    return rt[t]->qry(ql,qr);
  }
};
segtree t,t0;

void init(int N, std::vector<int> H) {
  n = N;
  h = H;
  //for(ll i = 0;i<n;i++) if((i==0||(h[i-1]<h[i]))&&(i==n-1||h[i]>h[i+1])) mx = i;
  //for(ll i = 1;i<n-1;i++){
  //  if (h[i-1]<h[i]&&h[i]>h[i+1]){
  //    ps.push_back(i);
  //  }
  //}
  //for(auto [u,v] : ps) cerr << "[" << u << "," << v << "]" << " ";cerr << "\n";
  lh.resize(n,0);
  rh.resize(n,0);
  hh.resize(n,0);
  {
    vector<pair<ll,ll>> v;
    v.push_back({h[0],h[0]});
    for(ll i = 1;i<n;i++){
      ll mi = h[i];
      while(v.size()&&v.back().first<h[i]){
        mi = min(mi,v.back().second);
        v.pop_back();
      }
      lh[i] = h[i]-mi;
      v.push_back({h[i],mi});
    }
  }
  {
    vector<pair<ll,ll>> v;
    v.push_back({h[n-1],h[n-1]});
    for(ll i = n-2;i>=0;i--){
      ll mi = h[i];
      while(v.size()&&v.back().first<h[i]){
        mi = min(mi,v.back().second);
        v.pop_back();
      }
      rh[i] = h[i]-mi;
      v.push_back({h[i],mi});
    }
  }
  for(ll i = 0;i<n;i++) hh[i] = min(lh[i],rh[i]);
  hs = hh;
  sort(hs.begin(),hs.end());
  hs.erase(unique(hs.begin(),hs.end()),hs.end());
  t = segtree(n);
  t0 = segtree(n);
  w = hs.size();
  vector<vector<ll>> adds(w);
  for(ll i = 0;i<n;i++){
    ll p = lower_bound(hs.begin(),hs.end(),hh[i])-hs.begin();
    adds[p].push_back(i);
  }
  for(ll i = w-1;i>=0;i--){
    t.nw();
    for(ll j : adds[i]){
      t.put(w-i,j);
      //cerr << "add " << hs[i] << " " << j << "\n";
    }
    //dat o = t.qry(w-i,0,n-1);
    //cerr << hs[i] << " " << o.l << " " << o.r << " " << o.c << "\n";
  }
  inc = decc = h;
  for(ll i = 1;i<n;i++) decc[i] = min(decc[i],decc[i-1]);
  for(ll i = n-2;i>=0;i--) inc[i] = min(inc[i],inc[i+1]);
  hhs = h;
  sort(hhs.begin(),hhs.end());
  hhs.erase(unique(hhs.begin(),hhs.end()),hhs.end());
  u = hhs.size();
  vector<vector<ll>> opp(u);
  for(ll i = 0;i<n;i++){
    ll p = lower_bound(hhs.begin(),hhs.end(),h[i])-hhs.begin();
    opp[p].push_back(i);
  }
  for(ll i = 0;i<u;i++){
    for(ll j : opp[i]){
      t0.put(i,j);
      //cerr << "add " << hs[i] << " " << j << "\n";
    }
    //dat o = t.qry(w-i,0,n-1);
    //cerr << hs[i] << " " << o.l << " " << o.r << " " << o.c << "\n";
    t0.nw();
  }
}
bool ps_inited = false;
void init_ps(ll d){
  ps_inited = true;
  vector<ll> ld(n,big),rd(n,big);
  {
    vector<pair<ll,ll>> v;
    v.push_back({h[0],0});
    for(ll i = 1;i<n;i++){
      auto it = lower_bound(v.begin(),v.end(),make_pair(h[i]-d+1,0));
      if (it!=v.begin()) ld[i] = i-(*--it).second;
      while(v.size()&&v.back().first>h[i]) v.pop_back();
      v.push_back({h[i],i});
    }
  }
  {
    vector<pair<ll,ll>> v;
    v.push_back({h[n-1],n-1});
    for(ll i = n-2;i>=0;i--){
      auto it = lower_bound(v.begin(),v.end(),make_pair(h[i]-d+1,0));
      if (it!=v.begin()) rd[i] = (*--it).second-i;
      while(v.size()&&v.back().first>h[i]) v.pop_back();
      v.push_back({h[i],i});
    }
  }
  for(ll i = 0;i<n;i++) if(lh[i]>=d&&rh[i]>=d) {
    ps.push_back(i);
    rgs.push_back({i-ld[i],i+rd[i]});
    //cerr << i-ld[i] << " " << i << " " << i+rd[i] << "\n";
  }
}

int max_towers(int L, int R, int D) {
  if(!ps_inited) init_ps(D);
  ll l = L, r = R, d = D;
  ll ans = 1;
  ll idx = w-(lower_bound(hs.begin(),hs.end(),d)-hs.begin());
  dat o = t.qry(idx,L,R);
  //cerr << idx << " " << L << " " << R << " " << o.l << " " << o.r << " " << o.c << "\n";
  if (o.c==0) return 1;
  ll cur = o.c;
  ll pl = upper_bound(hhs.begin(),hhs.end(),h[o.l]-d)-hhs.begin()-1;
  dat l_need = t0.qry(pl,0,o.l);
  if (l_need.r<L) cur--;
  ll pr = upper_bound(hhs.begin(),hhs.end(),h[o.r]-d)-hhs.begin()-1;
  dat r_need = t0.qry(pr,o.r,n-1);
  if (r_need.l>R) cur--;
  //ll l_need = upper_bound(inc.begin(),inc.begin(),h[o.l]-d)-inc.begin();
  //if (l_need-1<L) cur--;
  //ll r_need = lower_bound(decc.begin(),decc.end(),h[o.r]-d,greater<ll>())-decc.begin();
  //if (r_need>R) cur--;
  return 1+max(0,cur);
  //auto it0 = lower_bound(ps.begin(),ps.end(),r);
  //ll rf = it0-ps.begin();
  //auto it1 = lower_bound(ps.begin(),ps.end(),l+1);
  //ll lf = it1-ps.begin();
  //cerr << lf << " " << rf << "\n";
  //ans = max(0,rf-lf)+1;
  auto it0 = lower_bound(rgs.begin(),rgs.end(),make_pair(r,0));
  //if (it0!=rgs.begin()) --it0;
  ll rf = it0-rgs.begin();
  if (it0!=rgs.begin()){
    if ((*--it0).second>r) --rf;
  }
  auto it1 = lower_bound(rgs.begin(),rgs.end(),make_pair(l,0));
  ll lf = it1-rgs.begin();
  ans = max(0,rf-lf)+1;
  return ans;
  /*vector<obj> a,b;
  a.push_back({0,0});
  b.push_back({big,0});
  for(ll i = l;i<=r;i++){
    ll cur = 0;
    auto it = lower_bound(b.begin(),b.end(),obj({h[i]-1,0}),greater<obj>());
    --it;
    cur = (*it).c;
    ans = max(ans,cur+1);
    obj oa = {h[i],cur+1};
    if (a.size()<=oa.c) a.push_back(oa);
    else a[oa.c] = min(a[oa.c],oa);
    auto it0 = lower_bound(a.begin(),a.end(),obj({h[i]-d+1,0}));
    --it0;
    obj ob = {h[i]-d,(*it0).c};
    if (b.size()<=ob.c) b.push_back(ob);
    else b[ob.c] = max(b[ob.c],ob);
    ans = max(ans,cur+1);
    //cerr << "a:";for(auto [u,v] : a) cerr << "(" << u <<"," << v << ") ";cerr << "\n";
    //cerr << "b:";for(auto [u,v] : b) cerr << "(" << u <<"," << v << ") ";cerr << "\n";
  }*/
  return ans;
}

Compilation message (stderr)

towers.cpp: In constructor 'node::node(ll, ll)':
towers.cpp:41:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   node(ll a, ll b):l(a),r(b),m(a+b>>1),v(),L(nullptr),R(nullptr){
      |                                ~^~

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