Submission #1207937

#TimeUsernameProblemLanguageResultExecution timeMemory
1207937onbertTower (JOI24_tower)C++20
0 / 100
2096 ms7608 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 2e5 + 5, INF = 1e15; int n, q, d, a, b; vector<pair<int,int>> block, space; vector<int> qry; int belong(int i) { int id = lower_bound(block.begin(), block.end(), make_pair(i+1, -INF)) - block.begin() - 1; if (id >= 0 && i <= block[id].second) return id; else return -1; } int A(int x) { int ans = 0; while (x != 0) { int id = lower_bound(block.begin(), block.end(), make_pair(x, -INF)) - block.begin() - 1; ans += a * x - (block[id].second + 1); x = block[id].second + 1; if (x == 0) break; ans += b; x -= d; } return ans; } int B(int x) { int ans = 0; while (x != 0) { int id = lower_bound(block.begin(), block.end(), make_pair(x, -INF)) - block.begin() - 1; // cout << x << " " << id << endl; int jump = block[id].second - (block[id].second % d) + (x % d); if (jump <= block[id].second) jump += d; ans += b * (x - jump) / d; x = jump; if (id == 0) { ans += a * x, x = 0; break; } ans += b, x -= d; id = belong(x); if (id != -1) { ans += a * (x - (block[id].first - 1)); x = block[id].first - 1; } // cout << x << " " << ans << endl; } return ans; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> q >> d >> a >> b; n++; vector<pair<int,int>> vec(n); vec[0] = {-(d-1), -1}; for (int i=1;i<n;i++) cin >> vec[i].first >> vec[i].second; for (int i=0;i<n;i++) { auto [l, r] = vec[i]; if (block.size()) { if (r <= block.back().second) continue; else if (l - 1 <= block.back().second) { l = block.back().first; block.pop_back(); } } if ((r+1) - (l-1) > d) r = INF; else { int id = belong(r+1 - d); if (id != -1) r = block[id].second + d; } block.push_back({l, r}); // cout << i << " " << l << " " << r << endl; } n = block.size(); // for (auto [l, r]:vec) cout << l << " " << r << endl; while (q--) { int x; cin >> x; if (belong(x) != -1) cout << "-1\n"; else if (a * d <= b) cout << A(x) << "\n"; else cout << B(x) << "\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...