Submission #487365

#	Time	Username	Problem	Language	Result	Execution time	Memory
487365		leaked	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1092 ms	93936 KiB

skyscraper

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int K=100;
struct segtree{
    vec<int> ids;
    vec<pii>t;
    void build(int v,int t1,int t2,int tl,int tr){
        if(tl>tr) return;
        if(tl==tr){
            t[v]={2e9+t1*(ids[tl]/t2),ids[tl]};
            return;
        }
        int tm=(tl+tr)>>1;
        build(2*v,t1,t2,tl,tm);
        build(2*v+1,t1,t2,tm+1,tr);
        t[v]=max(t[2*v],t[2*v+1]);
    }
    void init(int t1,int t2){
        t.resize(sz(ids)*4);
        build(1,t1,t2,0,sz(ids)-1);
    }
    void upd(int id,int x,int v,int tl,int tr){
        if(tl==tr){
            assert(ids[tl]==id && t[v].f>x);
            t[v]={x,id};
//            cout<<"UPD "<<id<<' '<<x<<endl;
            return;
        }
        int tm=(tl+tr)>>1;
        if(ids[tm]>=id)
            upd(id,x,2*v,tl,tm);
        else
            upd(id,x,2*v+1,tm+1,tr);
        t[v]=max(t[2*v],t[2*v+1]);
    }
    pii get(int l,int r,int v,int tl,int tr){
        if(ids[tl]>=l&&ids[tr]<=r) return t[v];
        if(ids[tl]>r||ids[tr]<l) return {-2e9,1};
        int tm=(tl+tr)>>1;
        return max(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
    }
}lft[K][K],rgt[K][K];
/// nd+(i-j)<=d1
/// nd+i<=d1+1

void change(int id,int x){
    for(int j=1;j<K;j++){
        lft[j][id%j].upd(id,x+(id/j),1,0,sz(lft[j][id%j].ids)-1);
        rgt[j][id%j].upd(id,x-(id/j),1,0,sz(rgt[j][id%j].ids)-1);
    }
}
signed main(){
    fast_iati;
    int n,m;
    cin>>n>>m;
    vec<int>b(m),p(m);
    vec<vec<int>>have(n,vec<int>());
    for(int i=0;i<m;i++)
        cin>>b[i]>>p[i],have[b[i]].pb(i);
    priority_queue<pii,vec<pii>,greater<pii>>pq;
    for(int t=1;t<K;t++){
        for(int i=0;i<n;i++)
            lft[t][i%t].ids.pb(i),rgt[t][i%t].ids.pb(i);
        for(int j=0;j<t;j++){
            lft[t][j].init(+1,t),rgt[t][j].init(-1,t);
        }
    }
    vec<int>dp(n,2e9);
    pq.push({0,b[0]});
    dp[b[0]]=0;
    change(b[0],0);
    while(!pq.empty()){
        int v=pq.top().s;
        int x=pq.top().f;
        pq.pop();
        if(dp[v]!=x) continue;
        for(auto &u : have[v]){
            if(p[u]>=K){
                int j=b[u]-p[u];
                int cnt=1;
                while(j>=0){
                    if(umin(dp[j],dp[v]+cnt))
                        pq.push({dp[j],j}),change(j,dp[j]);
                    j-=p[u];cnt++;
                }
                j=b[u]+p[u];cnt=1;
                while(j<n){
                    if(umin(dp[j],dp[v]+cnt))
                        pq.push({dp[j],j}),change(j,dp[j]);
                    j+=p[u];cnt++;
                }
            }
            else{
                while(1){
                    pii js=lft[p[u]][b[u]%p[u]].get(0,b[u]-1,1,0,sz(lft[p[u]][b[u]%p[u]].ids)-1);
                    int f=js.f,j=js.s;
//                    if(v==37 && p[u]==5){
//                        cout<<"A E "<<j<<' '<<dp[v]+v<<' '<<' '<<f<<endl;
//                    }
                    if(dp[v]+v/p[u]<f){
                        umin(dp[j],dp[v]+((v-j)/p[u]));
                        change(j,dp[j]);
//                        if(v==37)cout<<"NEW "<<j<<' '<<dp[j]<<' '<<dp[v]<<' '<<dp[v]+((v-j)/p[u])<<' '<<v<<' '<<p[u]<<endl;
                        pq.push({dp[j],j});
                    }
                    else break;
                }
                while(1){
                    pii js=rgt[p[u]][b[u]%p[u]].get(b[u]+1,n-1,1,0,sz(rgt[p[u]][b[u]%p[u]].ids)-1);
                    int f=js.f,j=js.s;
//                    if(v==37){
//                        cout<<"A E "<<j<<' '<<dp[v]-v<<' '<<' '<<f<<endl;
//                    }
                    if(dp[v]-v/p[u]<f){
                        umin(dp[j],dp[v]+((j-v)/p[u]));
                        change(j,dp[j]);
                        pq.push({dp[j],j});
                    }
                    else break;
                }
            }
        }
    }
    cout<<(dp[b[1]]==2e9?-1:dp[b[1]]);
    return 0;
}
/*
6 1 3
8 1 2 1 5 4

5 3
0 2
1 1
4 1
dp[v]+(v-j)<=dp[j]
//dp[v]+v < dp[j]+
dp[v]-v<=dp[j]-j

*/

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43