Submission #1162384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162384		hengliao	Tower (JOI24_tower)	C++20	0 / 100	2095 ms	3768 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef long long ll;

const ll mxN=2e5+5;
const ll mxM=1e12+5;
const ll inf=2e18;

ll n, Q, d, a, b;

pll tep[mxN];
pll v[mxN];
ll q[mxN];
ll f[mxN];

void solve(){
    memset(f, -1, sizeof(f));
    cin>>n>>Q>>d>>a>>b;
    for(ll i=0;i<n;i++){
        cin>>tep[i].F>>tep[i].S;
    }
    // for(ll i=0;i<mxM;i++){
    //     dp[i]=inf;
    // }
    // dp[0]=0;
    // for(ll i=0;i<mxM;i++){
    //     if(!good[i]) continue;
    //     if(i+1<mxM && good[i+1]){
    //         dp[i+1]=min(dp[i+1], dp[i]+a);
    //     }
    //     if(i+d<mxM && good[i+d]){
    //         dp[i+d]=min(dp[i+d], dp[i]+b);
    //     }
    // }
    for(ll i=0;i<Q;i++){
        cin>>q[i];
    }
    // for(ll i=tep[n-1].F-1;i>=0;i--){
    //     if(!good[i]) continue;
    //     if(i+d<mxM && good2[i+d]){
    //         good2[i]=1;
    //     }
    //     else{
    //         good2[i]=0;
    //     }
    // }
    // memset(ans, -1, sizeof(ans));
    // ans[0]=0;
    v[0].F=0;
    v[0].S=tep[0].F-1;
    for(ll i=0;i<n-1;i++){
        v[i+1].F=tep[i].S+1;
        v[i+1].S=tep[i+1].F-1;
    }
    v[n].F=tep[n-1].S+1;
    v[n].S=mxM-1;
    f[0]=0;
    ll pt=0;
    for(ll i=1;i<=n;i++){
        while(pt<i && ((f[pt]==-1) || v[pt].S+d<v[i].F)){
            pt++;
        }
        if(f[pt]==-1) continue;
        if(f[pt]+d>v[i].S){
            continue;
        }
        if(v[i].F-d>=f[pt]){
            f[i]=v[i].F;
        }
        else{
            f[i]=f[pt]+d;
        }
    }
    // for(ll i=0;i<=n;i++){
    //     cout<<f[i]<<' '<<v[i].S<<'\n';
    // }
    auto reach=[&](ll tar){
        ll lef=0, rig=n;
        ll good=-1;
        while(lef<=rig){
            ll mid=(lef+rig)/2;
            if(v[mid].F<=tar){
                good=mid;
                lef=mid+1;
            }
            else{
                rig=mid-1;
            }
        }
        assert(good!=-1);
        if(f[good]==-1 || tar<f[good] || tar>v[good].S){
            return false;
        }
        return true;
    };
    for(ll i=0;i<Q;i++){
        ll lef=0, rig=n;
        ll good=-1;
        while(lef<=rig){
            ll mid=(lef+rig)/2;
            if(v[mid].F<=q[i]){
                good=mid;
                lef=mid+1;
            }
            else{
                rig=mid-1;
            }
        }
        assert(good!=-1);
        // if(f[good]!=-1 && q[i]>=f[good] && q[i]<=v[good].S){
        //     cout<<q[i]<<'\n';
        // }
        // else{
        //     cout<<-1<<'\n';
        // }
        if(f[good]==-1 || q[i]<f[good] || q[i]>v[good].S){
            cout<<-1<<'\n';
            continue;
        }
        if(a*d>b){
            ll cur=q[i];
            ll cnt=0;
            while(cur!=0){
                if(cur-d>=0 && reach(cur-d)){
                    cnt++;
                    cur-=d;
                }
                else{
                    assert(reach(cur-1));
                    cur--;
                }
            }
            cout<<cnt*b+(q[i]-(cnt*d))*a<<'\n';
        }
        else{
            ll cur=q[i];
            ll cnt=0;
            while(cur!=0){
                if(cur-1>=0 && reach(cur-1)){
                    cur--;
                }
                else{
                    assert(reach(cur-d));
                    cur-=d;
                    cnt++;
                }
            }
            cout<<cnt*b+(q[i]-(cnt*d))*a<<'\n';
        }
    }

    // ll lef=v[n].F:
    // ll rig=v[n].S;
    // for(ll i=)
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 38
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32