Submission #914739

#	Time	Username	Problem	Language	Result	Execution time	Memory
914739		vjudge1	Radio Towers (IOI22_towers)	C++17	100 / 100	892 ms	65856 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
using pl = pair<ll, ll>;
#define F(i, l, r) for (ll i = (l); i < (r); ++i)
#define FD(i, l, r) for (ll i = (l); i > (r); --i)
#define K first
#define V second

template<typename T> struct SparseTable {
    int n,log2=0;
    function<T(T, T)> merge;
    T id;
    vector<vector<T>> a = {{}};
    SparseTable(const vector<T>& v, function<T(T, T)> _merge, T _id): merge(_merge), id(_id) {
        n = v.size();
        while((1<<log2) <= n) {
            ++log2;
        }
        a.resize(log2);
        a[0] = v;
        for(int i=1,len=1;i<log2;++i,len*=2) {
            a[i].resize(n + 1 - (1<<i));
            for(size_t j=0;j<a[i].size();++j) {
                a[i][j] = merge(a[i-1][j], a[i-1][j + len]);
            }
        }
    }
    SparseTable(){}
    T query(int l, int r) { // [l,r)
        if (r <= l) return id;
        int len = __lg(r-l);
        return merge(a[len][l], a[len][r- (1<<len)]);
    }   
};

SparseTable<ll> spmin;
 
const int MAXN = 100010, INF = 1000000010;
 
struct node{
  vector<pl> vec;
  vector<int> mn, mx;
  node(){};
  node(int value, int pos){
    vec.emplace_back(value, pos);
    mn.push_back(pos);
    mx.push_back(pos);
  }
  node(node& a, node& b){
    vec.resize(a.vec.size() + b.vec.size());
    mn.resize(vec.size());
    mx.resize(vec.size());
    merge(a.vec.begin(), a.vec.end(), b.vec.begin(), b.vec.end(), vec.begin());
    int mi=MAXN, ma=-1;
    FD(i, ll(vec.size())-1, -1) {
      mi=min(mi, vec[i].V);
      ma=max(ma, vec[i].V);
      mn[i]=mi, mx[i]=ma;
    }
  }
};
 
int n, arr[MAXN], ml[MAXN], mr[MAXN], res[MAXN];
node tr[2*MAXN];
 
pair<int, pl> query(int l, int r, int x){
  int ret=0, mn=INF, mx=-1;
  for(l+=n, r+=n; l<r; l>>=1, r>>=1){
    if(l&1){
      auto itr = lower_bound(tr[l].vec.begin(), tr[l].vec.end(), pair(x, -1));
      int pos = (int)(itr - tr[l].vec.begin());
      ret += (int)(tr[l].vec.end() - itr);
      if(itr!=tr[l].vec.end()) mn=min(mn, tr[l].mn[pos]), mx=max(mx, tr[l].mx[pos]);
      ++l;
    }
    if(r&1){
      --r;
      auto itr = lower_bound(tr[r].vec.begin(), tr[r].vec.end(), pair(x, -1));
      int pos = (int)(itr - tr[r].vec.begin());
      ret += (int)(tr[r].vec.end() - itr);
      if(itr!=tr[r].vec.end()) mn=min(mn, tr[r].mn[pos]), mx=max(mx, tr[r].mx[pos]);
    }
  }
  return {ret, {mn, mx}};
}
 
void init(int N, vector<int> H) {
  n=N;
  F(i, 0, n) arr[i] = H[i];

  spmin = SparseTable<ll>(H, [](ll a, ll b) {
    return min(a, b);
  }, INF);
 
  F(i, 0, n) {
    int x;
    for(x=i-1; x!=-1 && H[x]<H[i]; x=ml[x]);
    ml[i]=x;
  }
 
  FD(i, n-1, -1) {
    int x;
    for(x=i+1; x!=n && H[x]<H[i]; x=mr[x]);
    mr[i]=x;
  }
  F(i, 0, n) {
    int l = ml[i], r = mr[i];
    int a = H[i] - spmin.query(l+1, i);
    int b = H[i] - spmin.query(i+1, r);
    res[i] = min(a, b);
  }
  F(i, 0, n)  tr[n+i]=node(res[i], i);
  
  FD(i, n-1, -1) tr[i]=node(tr[i<<1], tr[i<<1|1]);
}
 
int max_towers(int L, int R, int D) {
  pair<int, pl> ans = query(L, R+1, D);
  if(ans.K == 0) return 1;
  int sa = (spmin.query(L, ans.V.K) > arr[ans.V.K] - D);
  int sb = (spmin.query(ans.V.V+1, R+1) > arr[ans.V.V] - D);
  return max(0, ans.K - sa - sb) + 1;
}

• 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