제출 #811260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
811260		blackyuki	송신탑 (IOI22_towers)	C++17	100 / 100	976 ms	57668 KiB

towers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001;
#include "towers.h"
struct Sparsetable{
    ll n;
    vvi tablema,tablemi;
    vi sz;
    void init(vi v){
        n=v.size();
        tablema=vvi(18,vi(n));tablemi=vvi(18,vi(n));
        tablema[0]=tablemi[0]=v;
        rep(i,17)rep(j,n)if(j+(1<<(i+1))<=n){
            tablema[i+1][j]=max(tablema[i][j],tablema[i][j+(1<<i)]);
            tablemi[i+1][j]=min(tablemi[i][j],tablemi[i][j+(1<<i)]);
        }
        sz=vi(n+1);
        rep(i,18)REP(j,1<<i,1<<(i+1))if(j<=n)sz[j]=i;
    }
    ll getma(ll l,ll r){
        if(l>=r)return -inf;
        // ll res=-inf;
        // REP(i,l,r)chmax(res,tablema[0][i]);
        // return res;
        ///////////////////////////////////////////////////////////
        ll s=sz[r-l];
        return max(tablema[s][l],tablema[s][r-(1<<s)]);
    }
    ll getmi(ll l,ll r){
        if(l>=r)return inf;
        // ll res=inf;
        // REP(i,l,r)chmin(res,tablemi[0][i]);
        // return res;
        ///////////////////////////////////////////////////////////
        ll s=sz[r-l];
        return min(tablemi[s][l],tablemi[s][r-(1<<s)]);
    }
};
struct segtree{
    vvi seg;
    ll n;
    void init(vi v){
        n=v.size();
        seg=vvi(n*2);
        rep(i,n)seg[i+n].pb(v[i]);
        for(int i=n-1;i>0;i--){
            seg[i]=seg[i*2];
            for(ll x:seg[i*2+1])seg[i].pb(x);
            sort(all(seg[i]));
        }
    }
    ll get(ll l,ll r,ll D){
        ll ans=0;
        for(l+=n,r+=n;l<r;l>>=1,r>>=1){
            if(l&1){
                ans+=seg[l].size()-lb(seg[l],D);
                l++;
            }
            if(r&1){
                r--;
                ans+=seg[r].size()-lb(seg[r],D);
            }
        }
        return ans;
    }
};
vi v,sp,dif;
vvi L,R;
ll n,m;
Sparsetable sps;
segtree seg;
void init(int N,vector<int> H){
    for(int x:H)v.pb(-x);
    sps.init(v);
    n=N;
    rep(i,n)if((i==0||v[i-1]>v[i])&&(i==n-1||v[i+1]>v[i]))sp.pb(i);
    m=sp.size();
    L=vvi(18,vi(m,-1));R=vvi(18,vi(m,-1));
    {
        vi st;
        for(int i=m-1;i>=0;i--){
            while(st.size()&&v[sp[st.back()]]>v[sp[i]])st.pop_back();
            if(st.size())R[0][i]=st.back();
            st.pb(i);
        }
    }
    {
        vi st;
        rep(i,m){
            while(st.size()&&v[sp[st.back()]]>v[sp[i]])st.pop_back();
            if(st.size())L[0][i]=st.back();
            st.pb(i);
        }
    }
    rep(i,17)rep(j,m)if(L[i][j]!=-1)L[i+1][j]=L[i][L[i][j]];
    rep(i,17)rep(j,m)if(R[i][j]!=-1)R[i+1][j]=R[i][R[i][j]];
    dif=vi(m);
    rep(i,m){
        P rng;
        rng.fi=(L[0][i]==-1 ? 0 : sp[L[0][i]]+1);
        rng.se=(R[0][i]==-1 ? n-1 : sp[R[0][i]]-1);
        ll ma=min(sps.getma(rng.fi,sp[i]),sps.getma(sp[i]+1,rng.se+1));
        dif[i]=ma-v[sp[i]];
    }
    seg.init(dif);
}
int max_towers(int a, int b, int D){
    ll l=lb(sp,a),r=lb(sp,b+1)-1;
    if(l>r)return 1;
    ll l_=l,r_=r;
    if(sps.getma(a,sp[l])<v[sp[l]]+D){
        l_=l+1;
        ll cur=l;
        for(ll i=17;i>=0;i--){
            ll ncur=R[i][cur];
            if(ncur!=-1&&ncur<=r&&sps.getma(a,sp[ncur])<v[sp[ncur]]+D){
                cur=ncur;
                l_=cur+1;
            }
        }
    }
    if(sps.getma(sp[r]+1,b+1)<v[sp[r]]+D){
        r_=r-1;
        ll cur=r;
        for(ll i=17;i>=0;i--){
            ll ncur=L[i][cur];
            if(ncur!=-1&&ncur>=l&&sps.getma(sp[ncur]+1,b+1)<v[sp[ncur]]+D){
                cur=ncur;
                r_=cur-1;
            }
        }
    }
    // int ans=0;
    // REP(i,l_,r_+1)if(dif[i]>=D)ans++;
    // return ans+1;
    return seg.get(l_,r_+1,D)+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