#include <bits/stdc++.h>
#define pll pair<long long, long long>
using namespace std;
struct seg
{
long long l, r, val;
};
const long long inf=1e9;
pll a[200005];
long long b[200005], id[100005], ans[200005], check[500005];
vector<long long> v2;
vector<seg> v[2], v3[500005];
seg seg1, seg2;
bool sortt(long long x, long long y) {return b[x]<b[y];}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
long long n, q, d, x, y, m, i, j, k, sz1, sz2, id1, id2, dist;
cin >> n >> q >> d >> x >> y;
y=min(y, x*d);
for (i=1; i<=n; i++)
{
cin >> a[i].first >> a[i].second;
v2.push_back(a[i].first/d);
v2.push_back(a[i].second/d);
};
sort(a+1, a+n+1);
for (i=1; i<=q; i++)
{
cin >> b[i];
v2.push_back(b[i]/d);
id[i]=i; ans[i]=-1;
};
sort(id+1, id+q+1, sortt);
sort(v2.begin(), v2.end());
v2.erase(unique(v2.begin(), v2.end()), v2.end());
j=v2.size();
for (i=1; i<j; i++)
{
if (v2[i]!=v2[i-1]+1)
{
v2.push_back(v2[i-1]+1);
v2.push_back(v2[i]-1);
};
};
v2.push_back(0);
sort(v2.begin(), v2.end());
v2.erase(unique(v2.begin(), v2.end()), v2.end());
for (i=1; i<=n; i++)
{
j=lower_bound(v2.begin(), v2.end(), a[i].first/d)-v2.begin();
k=lower_bound(v2.begin(), v2.end(), a[i].second/d)-v2.begin();
if (j==k) {v3[j].push_back({a[i].first%d, a[i].second%d, -1});}
else if (j+1<k) {v3[j].push_back({a[i].first%d, d-1, -1}); check[j+1]=1;}
else
{
v3[j].push_back({a[i].first%d, d-1, -1});
v3[k].push_back({0, a[i].second%d, -1});
};
};
if (v3[0].size() && v3[0][0].l==0) {v[0].push_back({0, d-1, -1});}
else if (v3[0].size())
{
v[0].push_back({0, v3[0][0].l-1, 0});
v[0].push_back({v3[0][0].l, d-1, -1});
}
else {v[0].push_back({0, d-1, 0});};
m=v2.size(); j=1;
for (i=0; i<m; i++)
{
if (check[i]==1) {break;};
if (i>0)
{
dist=y*(v2[i]-v2[i-1]);
v[i%2].clear();
sz1=v[1-i%2].size(); sz2=v3[i].size();
id1=id2=0;
if (v[1-i%2][0].val==-1 && v[1-i%2].back().val!=-1 && (v3[i].empty() || v3[i][0].l!=0)) {v[1-i%2][0].val=v[1-i%2].back().val+(d-v[1-i%2].back().l)*x-y;};
while (id1<sz1 || id2<sz2)
{
if (id1<sz1) {seg1=v[1-i%2][id1];};
if (id2<sz2) {seg2=v3[i][id2];};
if (id1==sz1)
{
if (!v[i%2].empty() && v[i%2].back().val==-1) {v[i%2].back().r=d-1;}
else {v[i%2].push_back({seg2.l, d-1, -1});};
id2=sz2;
}
else if (id2==sz2)
{
if (seg1.val==-1)
{
if (v[i%2].empty()) {v[i%2].push_back(seg1);}
else {v[i%2].back().r=max(v[i%2].back().r, seg1.r);};
}
else
{
if (v[i%2].empty()) {v[i%2].push_back({seg1.l, seg1.r, seg1.val+dist});}
else if (v[i%2].back().val==-1 && v[i%2].back().r<seg1.r) {v[i%2].push_back({v[i%2].back().r+1, seg1.r, seg1.val+dist+(v[i%2].back().r+1-seg1.l)*x});}
else if (v[i%2].back().val==-1) {v[i%2].back().r=max(v[i%2].back().r, seg1.r);}
else {v[i%2].push_back({seg1.l, seg1.r, seg1.val+dist});};
};
id1++;
}
else if (seg1.l<seg2.l)
{
if (seg1.val==-1)
{
if (v[i%2].empty()) {v[i%2].push_back(seg1);}
else if (seg1.r<seg2.l) {v[i%2].back().r=max(v[i%2].back().r, seg1.r);}
else {v[i%2].back().r=max(v[i%2].back().r, seg2.l-1);};
}
else if (v[i%2].empty())
{
if (seg1.r>seg2.r) {v[i%2].push_back({seg1.l, seg2.l-1, seg1.val+dist}); v[1-i%2][id1].val+=(seg2.r+1-seg1.l)*x; v[1-i%2][id1].l=seg2.r+1; continue;}
else if (seg1.r<seg2.l) {v[i%2].push_back({seg1.l, seg1.r, seg1.val+dist});}
else {v[i%2].push_back({seg1.l, seg2.l-1, seg1.val+dist});};
}
else
{
if (v[i%2].back().val==-1 && v[i%2].back().r<seg1.r)
{
if (seg1.r>seg2.r) {v[i%2].push_back({v[i%2].back().r+1, seg2.l-1, seg1.val+dist+(v[i%2].back().r+1-seg1.l)*x}); v[1-i%2][id1].val+=(seg2.r+1-seg1.l)*x; v[1-i%2][id1].l=seg2.r+1; continue;}
else if (seg1.r<seg2.l) {v[i%2].push_back({v[i%2].back().r+1, seg1.r, seg1.val+dist+(v[i%2].back().r+1-seg1.l)*x});}
else {v[i%2].push_back({v[i%2].back().r+1, seg2.l-1, seg1.val+dist+(v[i%2].back().r+1-seg1.l)*x});};
}
else if (v[i%2].back().val==-1) {v[i%2].back().r=max(v[i%2].back().r, seg1.r);}
else if (seg1.r>seg2.r) {v[i%2].push_back({seg1.l, seg2.l-1, seg1.val+dist}); v[1-i%2][id1].val+=(seg2.r+1-seg1.l)*x; v[1-i%2][id1].l=seg2.r+1; continue;}
else if (seg1.r<seg2.l) {v[i%2].push_back({seg1.l, seg1.r, seg1.val+dist});}
else {v[i%2].push_back({seg1.l, seg2.l-1, seg1.val+dist});};
};
id1++;
}
else
{
if (!v[i%2].empty() && v[i%2].back().val==-1) {v[i%2].back().r=max(v[i%2].back().r, seg2.r);}
else {v[i%2].push_back(seg2);};
id2++;
};
};
};
k=0;
while (j<=q && b[id[j]]/d==v2[i])
{
while (k<(long long)v[i%2].size() && v[i%2][k].r<b[id[j]]%d) {k++;};
if (v[i%2][k].val==-1) {ans[id[j]]=-1;}
else {ans[id[j]]=v[i%2][k].val+(b[id[j]]%d-v[i%2][k].l)*x;};
j++;
};
};
for (i=1; i<=q; i++) {cout << ans[i] << "\n";};
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |