제출 #707347

#제출 시각아이디문제언어결과실행 시간메모리
707347StickfishJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1085 ms124856 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; 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); if (it != active.end()) best.erase({get_value(*it), *it}); if (it != active.begin()) best.erase({get_value(*prev(it)), *prev(it)}); pivots.insert(lower_bound(pivots.begin(), pivots.end(), pair<int, int>{x, -1}), {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() { 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() { 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; 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...