제출 #811250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
811250		blackyuki	송신탑 (IOI22_towers)	C++17	41 / 100	4065 ms	45936 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)]);
    }
};
vi v,sp,dif;
vvi L,R;
ll n,m;
Sparsetable sps;
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]];
    }
}
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;
    {
        int cur=l;
        while(cur!=-1&&cur<=r){
            if(sps.getma(a,sp[cur])>=v[sp[cur]]+D)break;
            l_=cur+1;
            cur=R[0][cur];
        }
    }
    {
        int cur=r;
        while(cur!=-1&&cur>=l){
            if(sps.getma(sp[cur]+1,b+1)>=v[sp[cur]]+D)break;
            r_=cur-1;
            cur=L[0][cur];
        }
    }
    int ans=0;
    REP(i,l_,r_+1)if(dif[i]>=D)ans++;
    return ans+1;
}

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