Submission #1207489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207489		lighton	Tower (JOI24_tower)	C++20	43 / 100	2094 ms	88948 KiB

Main

#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
ll N,Q,D,A,B;
ll L[200001],R[200001],G[200001];
vector<ll> X,Y;
vector<array<ll,2> > block[1000001];
vector<array<ll,2> > query[1000001];
ll arr[1000001];
ll ans[1000001];
ll blk[1000001];

int main(){
    cin>>N>>Q>>D>>A>>B;
    forf(i,1,N) {
        cin >> L[i] >> R[i];
        X.pb({L[i] % D}), X.pb({R[i] % D}), X.pb({(L[i]-1)%D}), X.pb({(R[i]+1)%D});
        Y.pb({L[i]/D}), Y.pb({L[i]/D + 1}); if(L[i]/D != 0) Y.pb({L[i]/D-1});
    }
    forf(i,1,Q) cin>>G[i], X.pb({G[i]%D}), Y.pb({G[i]/D});
    X.pb(0), X.pb(D-1), Y.pb(0);
    sort(all(X)), comp(X), sort(all(Y)), comp(Y);

    forf(i,1,N){
        if(L[i]/D != R[i]/D) {
            block[idx(L[i] / D, Y)].pb({idx(L[i] % D ,X), sz(X)-1});
            if(R[i]-L[i]+1 >= D) block[idx(L[i]/D + 1, Y)]. pb({0,sz(X)-1});
            else block[idx(L[i] / D + 1,Y)].pb({0, idx(R[i]%D, X)});
        }
        else block[idx(L[i] / D, Y)].pb({idx(L[i] % D ,X), idx(R[i] % D ,X)});
    }
    forf(i,1,Q) query[idx(G[i]/D,Y)].pb({idx(G[i]%D, X), i});

    forf(i,1,sz(X)-1) arr[i] = inf;
    forf(y,0,sz(Y)-1){
        ll step = 1;
        if(y != 0) step = Y[y] - Y[y-1];
        if(y != 0) arr[0] = min(arr[0] + B*step, arr[sz(X)-1] + min(A + B*(step-1), A + A*D*(step-1)));

        forf(i,0,sz(X)-1) blk[i] = 0;
        for(auto [s,e] : block[y]) forf(i,s,e) blk[i] = 1, arr[i] = inf;

        forf(i,1,sz(X)-1) if(!blk[i]) arr[i] = arr[i]+B*step;
        forf(i,1,sz(X)-1) if(!blk[i]) arr[i] = min(arr[i], arr[i-1]+A*(X[i]-X[i-1]));

        for(auto [x,i] : query[y]) ans[i] = arr[x];
    }
    forf(i,1,Q){
        if(ans[i] >= inf) cout<<"-1\n";
        else cout<<ans[i]<<"\n";
    }
}

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