제출 #707357

#제출 시각아이디문제언어결과실행 시간메모리
707357StickfishJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1081 ms71476 KiB
#include <iostream> #include <vector> #include <set> #include <algorithm> #include <bitset> using namespace std; const int MAXN = 30100; const int SQN = 50; const int INF = 1e9 + 177013; pair<int, int> dogs[MAXN]; vector<int> jlen[MAXN]; struct modmin { void resize(int n) { sz = n; for (int i = 0; i < n; ++i) active.insert(i); pivots = {{-INF, 10}, {INF, 10}}; } void insert_pivot(int x, int vl) { auto it = active.lower_bound(x); pivots.insert({x, vl}); if (it != active.end()) best.insert({get_value(*it), *it}); if (it != active.begin()) best.insert({get_value(*prev(it)), *prev(it)}); } void deactivate(int x) { int vl = get_value(x); auto it = active.find(x); if (best.find({vl, x}) != best.end()) { best.erase({vl, x}); if (next(it) != active.end()) best.insert({get_value(*next(it)), *next(it)}); if (it != active.begin()) best.insert({get_value(*prev(it)), *prev(it)}); } active.erase(it); } pair<int, int> get_min() { while (best.size()) { auto [yvl, y] = *best.begin(); if (active.find(y) == active.end()) { best.erase(best.begin()); } else { break; } } if (best.empty()) return {INF, INF}; return *best.begin(); } private: int sz; set<pair<int, int>> pivots; set<int> active; set<pair<int, int>> best; int get_value(int x) { auto it = pivots.lower_bound({x, -1}); return min(get_transit(it, x), get_transit(prev(it), x)); } int get_transit(set<pair<int, int>>::iterator it, int x) { return abs(x - it->first) + it->second; } }; bitset<MAXN> used; int dist_long[MAXN]; modmin dist_short[SQN][SQN]; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 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; set<pair<int, int>> rdist_long; rdist_long.insert({0, s}); int T = n; while (T--) { pair<int, int> opt = {INF, INF}; if (rdist_long.size()) opt = *rdist_long.begin(); if (rdist_short.size()) opt = min(opt, *rdist_short.begin()); auto [dist, v] = opt; if (dist >= INF) break; rdist_long.erase({dist_long[v], v}); dist_long[v] = dist; if (used[v]) { cout << "ERROR" << endl; return 1; } 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); } sort(jlen[v].begin(), jlen[v].end()); jlen[v].resize(unique(jlen[v].begin(), jlen[v].end()) - jlen[v].begin()); for (auto p : jlen[v]) { if (p >= SQN) { for (int k = 1; p * k <= v; ++k) { if (used[v - p * k]) continue; rdist_long.erase({dist_long[v - p * k], v - p * k}); dist_long[v - p * k] = min(dist_long[v - p * k], dist + k); rdist_long.insert({dist_long[v - p * k], v - p * k}); } for (int k = 1; v + p * k < n; ++k) { if (used[v + p * k]) continue; rdist_long.erase({dist_long[v + p * k], v + p * k}); dist_long[v + p * k] = min(dist_long[v + p * k], dist + k); rdist_long.insert({dist_long[v + p * k], v + p * k}); } } else { int md = v % p; 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); } } //cout << "HIE" << endl; } 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...