Submission #1162303

#TimeUsernameProblemLanguageResultExecution timeMemory
1162303hengliaoTower (JOI24_tower)C++20
5 / 100
49 ms15688 KiB
#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=1e6+5;
const ll inf=2e18;

ll n, Q, d, a, b;

pll tep[mxN];
ll q[mxN];
ll dp[mxM];
bool good[mxM];

void solve(){
    cin>>n>>Q>>d>>a>>b;
    for(ll i=0;i<mxM;i++){
        good[i]=1;
    }
    for(ll i=0;i<n;i++){
        cin>>tep[i].F>>tep[i].S;
        for(ll j=tep[i].F;j<=tep[i].S;j++){
            good[j]=0;
        }
    }
    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];
        if(dp[q[i]]==inf){
            cout<<-1<<'\n';
        }
        else{
            cout<<dp[q[i]]<<'\n';
        }
    }
    // 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;
    // 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...