Submission #914783

#	Time	Username	Problem	Language	Result	Execution time	Memory
914783		vjudge1	Radio Towers (IOI22_towers)	C++17	100 / 100	978 ms	66336 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define F(i, l, r) for (ll i = ll(l); i < ll(r); ++i)
#define FD(i, l, r) for (ll i = ll(l); i > ll(r); --i)
#define A(a) (a).begin(), (a).end()
#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;

namespace seg {
    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;
            }
        }
    };

    node tr[2*MAXN];

    pair<int, pl> query(int l, int r, int x){
        int ret=0, mn=INF, mx=-1;

        auto handle = [&](node& cur) {
            auto itr = lower_bound(A(cur.vec), pair(x, -1));
            int pos = (int)(itr - cur.vec.begin());
            ret += (int)(cur.vec.end() - itr);
            if(itr!=cur.vec.end()) mn=min(mn, cur.mn[pos]), mx=max(mx, cur.mx[pos]);
        };

        for(l+=MAXN, r+=MAXN; l<r; l>>=1, r>>=1){
            if(l&1) handle(tr[l++]);
            if(r&1) handle(tr[--r]);
        }

        return {ret, {mn, mx}};
    }

    void build(vl res) {
        F(i, 0, res.size()) seg::tr[MAXN+i]=seg::node(res[i], i);
        FD(i, MAXN-1, -1) tr[i]=node(tr[i<<1], tr[i<<1|1]);
    }
}
 
 
int arr[MAXN];
 
void init(int n, vector<int> H) {
    vl maxl(n), maxr(n);
    copy(A(H), arr);

    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=maxl[x]);
        maxl[i]=x;

        if (~x) assert(H[x] > H[i]);
    }

    FD(i, n-1, -1) {
        int x;
        for(x=i+1; x!=n && H[x]<H[i]; x=maxr[x]);
        maxr[i]=x;
    }

    vl res(n);

    F(i, 0, n) {
        int l = maxl[i], r = maxr[i];
        int a = H[i] - spmin.query(l+1, i);
        int b = H[i] - spmin.query(i+1, r);
        res[i] = min(a, b);
    }

    seg::build(res);
}
 
int max_towers(int L, int R, int D) {
  pair<int, pl> ans = seg::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