Submission #1207950

#TimeUsernameProblemLanguageResultExecution timeMemory
1207950onbertTower (JOI24_tower)C++20
100 / 100
164 ms20288 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; 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 bef(int x) { return lower_bound(block.begin(), block.end(), make_pair(x, -INF)) - block.begin() - 1; } int nxt(int x, int mod) { int val = x - (x % d) + (mod % d); if (val < x) val += d; return val; } vector<int> ansA; int Aqry(int x) { int id = bef(x); return ansA[id] + a * (x - (block[id].second + 1)); } void A() { ansA.resize(n); ansA[0] = 0; for (int i=1;i<n;i++) ansA[i] = Aqry((block[i].second+1) - d) + b; while (q--) { int x; cin >> x; if (belong(x) != -1) cout << "-1\n"; else cout << Aqry(x) << "\n"; } } vector<vector<pair<int,int>>> qry; vector<int> ansB; set<pair<int,int>> s; void ins(int l, int r, int id) { int last = -1; while (true) { auto it = s.lower_bound({l, -INF}); if (it == s.end() || (it->first) > r+1) break; last = it->second; s.erase(it); } s.insert({l, id}); if (last == -1) { int id = prev(s.lower_bound({l, id}))->second; s.insert({r+1, id}); } if (r != d-1 && last != -1) s.insert({r+1, last}); } int Bqry(int x) { int ans = 0; int id = prev(s.lower_bound({x%d+1, -INF}))->second; if (id == 0) return a * (x%d) + b * (x/d); int jump = nxt(block[id].first, x); ans += b * ((x - jump) / d); x = jump; ans += a * (x - (block[id].first - 1)); x = block[id].first - 1; ans += ansB[id]; return ans; } void B() { qry.resize(n); ansB.resize(n); vector<int> ans(q); for (int i=0;i<q;i++) { int x; cin >> x; if (belong(x) != -1) { ans[i] = -1; continue; } int id = bef(x); qry[id].push_back({x, i}); } s.insert({0, 0}); for (int i=0;i<n;i++) { if (i != 0) { int l = block[i].first % d, r = block[i].second % d; if (l <= r) ins(l, r, i); else { ins(l, d-1, i); ins(0, r, i); } } // cout << i << " " << ansB[i] << endl; // for (auto [pos, ID]:s) cout << pos << "." << ID << " "; cout << endl; for (auto [x, id]:qry[i]) ans[id] = Bqry(x); if (i+1 < n) ansB[i+1] = Bqry(block[i+1].first - 1); } for (int i:ans) cout << i << "\n"; } 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}); } n = block.size(); if (a * d <= b) A(); else B(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...