Submission #707339

#TimeUsernameProblemLanguageResultExecution timeMemory
707339StickfishJakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
1033 ms6968 KiB
#include <iostream> #include <vector> #include <set> #include <algorithm> #include <bitset> using namespace std; const int MAXN = 30100; const int SQN = 200; const int INF = 1e9 + 177013; pair<int, int> dogs[MAXN]; vector<int> jlen[MAXN]; struct modmin { void resize(int n) { sz = n; used.resize(sz); pivots = {{-INF, 10}, {INF, 10}}; } void insert_pivot(int x, int vl) { pivots.insert(lower_bound(pivots.begin(), pivots.end(), pair<int, int>{x, -1}), {x, vl}); } void deactivate(int x) { used[x] = 1; } pair<int, int> get_min() { int i = 0; pair<int, int> ans = {INF, INF}; for (int x = 0; x < sz; ++x) { if (pivots[i].first == INF) break; if (x - pivots[i].first + pivots[i].second > pivots[i + 1].first - x + pivots[i + 1].second) ++i; if (!used[x]) ans = min(ans, {abs(x - pivots[i].first) + pivots[i].second, x}); } return ans; } //private: int sz; vector<pair<int, int>> pivots; vector<bool> used; }; bitset<MAXN> used; int dist_long[MAXN]; modmin dist_short[SQN][SQN]; signed main() { int n, m; cin >> n >> m; for (int i = 0; i < m; ++i) { cin >> dogs[i].first >> dogs[i].second; jlen[dogs[i].first].push_back(dogs[i].second); } int s = dogs[0].first; int t = dogs[1].first; for (int i = 0; i < n; ++i) dist_long[i] = INF; dist_long[s] = 0; for (int d = 1; d < SQN; ++d) { for (int md = 0; md < n && md < d; ++md) { dist_short[d][md].resize((n - md - 1) / d + 1); } } set<pair<int, int>> rdist_short; int T = n; while (T--) { //cout << "A" << endl; pair<int, int> opt = {INF, INF}; for (int i = 0; i < n; ++i) { if (!used[i]) opt = min(opt, {dist_long[i], i}); } if (rdist_short.size()) { opt = min(opt, *rdist_short.begin()); } auto [dist, v] = opt; if (dist >= INF) break; dist_long[v] = dist; used[v] = 1; for (int d = 1; d < SQN; ++d) { int md = v % d; pair<int, int> cval = dist_short[d][md].get_min(); cval.second = md + d * cval.second; rdist_short.erase(cval); dist_short[d][md].deactivate(v / d); pair<int, int> ncval = dist_short[d][md].get_min(); ncval.second = md + d * ncval.second; rdist_short.insert(ncval); } for (auto p : jlen[v]) { if (p >= SQN) { for (int k = 1; p * k <= v; ++k) dist_long[v - p * k] = min(dist_long[v - p * k], dist + k); for (int k = 1; v + p * k < n; ++k) dist_long[v + p * k] = min(dist_long[v + p * k], dist + k); } else { int md = v % p; //cout << "! " << p << ' ' << md << endl; pair<int, int> cval = dist_short[p][md].get_min(); cval.second = md + p * cval.second; rdist_short.erase(cval); dist_short[p][md].insert_pivot(v / p, dist); pair<int, int> ncval = dist_short[p][md].get_min(); ncval.second = md + p * ncval.second; rdist_short.insert(ncval); } } } if (dist_long[t] >= INF) cout << "-1\n"; else cout << dist_long[t] << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...