제출 #1183565

#제출 시각아이디문제언어결과실행 시간메모리
1183565dragstTower (JOI24_tower)C++20
0 / 100
1176 ms20120 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...