제출 #1241450

#제출 시각아이디문제언어결과실행 시간메모리
1241450HanksburgerTower (JOI24_tower)C++20
0 / 100
37 ms6316 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
int cutoff[200005], jumps[200005], ans[200005];
vector<pair<int, int> > vec, z;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q, a, b, d;
    cin >> n >> q >> d >> a >> b;
    vec.push_back({-1e18, -1});
    for (int i=1; i<=n; i++)
    {
        int l, r;
        cin >> l >> r;
        vec.push_back({l, r});
    }
    vec.push_back({1e18, 2e18});
    for (int i=0; i<q; i++)
    {
        int x;
        cin >> x;
        z.push_back({x, i});
    }
    sort(z.begin(), z.end());
    if (a*d<=b)
    {
        for (int i=2; i<=n+1; i++)
        {
            int ind=lower_bound(vec.begin(), vec.end(), make_pair(vec[i-1].second-d+2, 0LL))-vec.begin();
            if (ind==i)
                cutoff[i]=1e18;
            else
            {
                cutoff[i]=max(vec[i-1].second+1, cutoff[ind]+d);
                jumps[i]=jumps[ind]+1;
            }
        }
        int ind=1;
        for (int i=0; i<q; i++)
        {
            while (vec[ind].first<=z[i].first)
                ind++;
            if (z[i].first<cutoff[ind])
                ans[z[i].second]=-1;
            else
                ans[z[i].second]=jumps[ind]*b+(z[i].first-jumps[ind]*d)*a;
        }
        for (int i=0; i<q; i++)
            cout << ans[i] << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...