Submission #627357

#	Time	Username	Problem	Language	Result	Execution time	Memory
627357		ainta	Radio Towers (IOI22_towers)	C++17	100 / 100	1837 ms	52756 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
 
using ll=long long;
 
 
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned ll;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
#define N_ 101000
#define SZ 131072

int chk, w[N_], n, INF = 1e9 + 123;
//vi V;

struct Tree{
  pii IT[SZ+SZ];
  void Put(int a, int b){
    IT[a+SZ]={b,a};
    a+=SZ;
    while(a!=1){
      a>>=1;
      IT[a]=max(IT[a*2],IT[a*2+1]);
    }
  }
  pii Get(int b, int e){
    pii r={-INF,0};
    b+=SZ,e+=SZ;
    while(b<=e){
      r=max({r,IT[b],IT[e]});
      b=(b+1)>>1,e=(e-1)>>1;
    }
    return r;
  }
}T1,T2,U1,U2;

pii Max(int b, int e){
  return T1.Get(b,e);
}
pii Min(int b, int e){
  auto z = T2.Get(b,e);
  return {-z.fi, z.se};
}

struct Node{
  pii Mn, Mx;
  t3 ud, du;
}IT[SZ+SZ];
Node Merge (Node a, Node b){
  Node r;
  r.Mn = min(a.Mn,b.Mn);
  r.Mx = max(a.Mx,b.Mx);
  r.ud = max({a.ud, b.ud, {a.Mx.fi - b.Mn.fi, a.Mx.se, b.Mn.se} });
  r.du = max({a.du, b.du, {b.Mx.fi - a.Mn.fi, a.Mn.se, b.Mx.se} });
  return r;
}

void Put(int a){
  Node t = {{w[a],a}, {w[a],a}, {0,a,a}, {0,a,a}};
  a+=SZ;
  IT[a] = t;
  while(a!=1){
    a>>=1;
    IT[a] = Merge(IT[a*2],IT[a*2+1]);
  }
}
Node GetRange(int b, int e){
  b+=SZ,e+=SZ;
  vi TL, TR;
  while(b<=e){
    if(b&1)TL.pb(b);
    if(!(e&1))TR.pb(e);
    b=(b+1)>>1,e=(e-1)>>1;
  }
  reverse(all(TR));
  for(auto &t : TR)TL.pb(t);
  Node res = IT[TL[0]];
  rng(i,1,si(TL)-1){
    res = Merge(res, IT[TL[i]]);
  }
  return res;
}

int U[N_];
int isUp[N_];

priority_queue<t3>PQ;
set<int>Set;
void SetPut(int x, int d){
  auto it = Set.find(x);
  auto it2 = it;
  auto it3 = it;
  it2--;
  it3++;

  if(*it2 == 0){
    if(x>1){
      if(isUp[x]){
        auto [gg,u] = Min(1,x-1);
        if(w[x] > w[u]){
          PQ.push({w[x]-w[u], 0, u});
        }
      }
      else{
        auto [gg,u] = Max(1,x-1);
        if(w[x] < w[u]){
          PQ.push({w[u]-w[x], 0, u});
          isUp[u] = 1;
        }
      }
    }
  }
  else{
    int b = (*it2) + 1, e = (*it)-1;

    if(b<=e){
      if(isUp[x]){
        auto [p1,p2,p3,p4] = GetRange(b,e);
        if(get<0>(p3)>0){
          PQ.push(p3);
          isUp[get<1>(p3)] = 1;
        }
      }
      else{
        auto [p1,p2,p3,p4] = GetRange(b,e);
        if(get<0>(p4)>0){
          PQ.push(p4);
          isUp[get<2>(p4)] = 1;
        }
      }
    }
  }
  if(*it3 == n+1){
    if(x<n){
      if(isUp[x]){
        auto [gg,u] = Min(x+1,n);
        if(w[x] > w[u]){
          PQ.push({w[x]-w[u], 0, u});
        }
      }
      else{
        auto [gg,u] = Max(x+1,n);
        if(w[x] < w[u]){
          PQ.push({w[u]-w[x], 0, u});
          isUp[u] = 1;
        }
      }
    }

  }
  else{
    int b = (*it) + 1, e = (*it3)-1;

    if(b<=e){
      if(!isUp[x]){
        auto [p1,p2,p3,p4] = GetRange(b,e);
        if(get<0>(p3)>0){
          PQ.push(p3);
          isUp[get<1>(p3)] = 1;
        }
      }
      else{
        auto [p1,p2,p3,p4] = GetRange(b,e);
        if(get<0>(p4)>0){
          PQ.push(p4);
          isUp[get<2>(p4)] = 1;
        }
      }
    }
  }
}

int Root[N_];
struct PNode{
  int l, r, s;
};
PNode PST[N_*30];
int cnt;

void Add(int nd, int p, int l, int r, int x){
  PST[nd] = PST[p];
  int m = (l+r)>>1;
  PST[nd].s++;
  if(l==r)return;
  if(x<=m){
    PST[nd].l = ++cnt;
    Add(PST[nd].l, PST[p].l, l, m, x);
  }
  else{
    PST[nd].r = ++cnt;
    Add(PST[nd].r, PST[p].r, m+1, r, x);
  }
}

int Sum(int nd, int b, int e, int s, int l){
  if(s<=b&&e<=l)return PST[nd].s;
  if(s>l)return 0;
  int m = (b+e)>>1;
  int rr = 0;
  if(s<=m)rr += Sum(PST[nd].l, b, m, s, l);
  if(l>m) rr += Sum(PST[nd].r, m+1, e, s, l);
  return rr;
}


int Left(int nd, int b, int e, int s, int l){
  if(!PST[nd].s)return -1;
  if(b==e)return b;
  int m = (b+e)>>1;
  int rr = 0;
  if(s<=m){
    rr = Left(PST[nd].l, b, m, s, l);
    if(rr!=-1)return rr;
  }
  return Left(PST[nd].r, m+1, e, s, l);
}
int Right(int nd, int b, int e, int s, int l){
  if(!PST[nd].s)return -1;
  if(b==e)return b;
  int m = (b+e)>>1;
  int rr = 0;
  if(l>m){
    rr = Right(PST[nd].r, m+1, e, s, l);
    if(rr!=-1)return rr;
  }
  return Right(PST[nd].l, b, m, s, l);
}

vc<pii>V;

void init(int N, std::vector<int> H) {
  n = N;
  rng(i,1,N){
    w[i] = H[i-1];
    T1.Put(i,w[i]);
    T2.Put(i,-w[i]);
  }
  rng(i,1,n){
    Put(i);
  }
  auto [p1, p2, p3, p4] = GetRange(1,n);
  Set.insert(0);
  Set.insert(n+1);
  {
    if(get<0>(p3) < get<0>(p4)){
      PQ.push(p4);
      isUp[get<2>(p4)] = 1;
    }
    else{
      PQ.push(p3);
      isUp[get<1>(p3)] = 1;
    }
  }
  while(!PQ.empty()){
    
    auto [d,l,r] = PQ.top();
    //printf("! %d %d %d\n",d,l,r);
    PQ.pop();
    if(l!=0){
      Set.insert(l);
      if(!U[l])U[l] = d;
    }
    Set.insert(r);
    if(!U[r])U[r] = d;
    if(l)SetPut(l,d);
    SetPut(r,d);
  }
  rng(i,1,n){
    V.pb({U[i],i});
    U1.Put(i, U[i]);
  }
  sort(all(V));
  per(i,n){
    Root[i] = ++cnt;
    Add(Root[i], Root[i+1], 1, n, V[i].se);
  }
}


int max_towers(int L, int R, int D) {
  L++,R++;
  int pv = lower_bound(all(V), pii(D,-999)) - V.begin();
  int c = Sum(Root[pv], 1, n, L, R);
  if(!c)return 1;

  int bb = Left(Root[pv], 1, n, L, R);
  int ee = Right(Root[pv], 1, n, L, R);

  if(isUp[bb]){
    if(w[bb] - Min(L,bb-1).fi>= D) c++;
    else c--;
  }
  if(isUp[ee]){
    if(w[ee] - Min(ee+1,R).fi>= D) c++;
    else c--;
  }
  return max(1,(c+1)/2);
}

• 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