| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 564044 | 2022-05-18T13:29:37 Z | Cyanmond | Jakarta Skyscrapers (APIO15_skyscraper) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
constexpr int inf = 1 << 30;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)
#define ALL(x) (x).begin(), (x).end()
template <typename T> bool chmin(T &a, const T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
constexpr int V = 15000000;
int main() {
int N, M;
cin >> N >> M;
vector<pair<short, short>> A(M);
REP(i, M) {
cin >> A[i].first >> A[i].second;
chmin(A[i].second, (short)N);
}
int S = 0, T = 0;
{
const auto as = A[0], at = A[1];
sort(ALL(A), [](auto a, auto b) {
if (a.second != b.second) {
return a.second < b.second;
}
return a.first < b.first;
});
REP(i, M) {
if (A[i] == as) S = i;
if (A[i] == at) T = i;
}
}
static array<vector<pair<short, bool>>, 30010> lst(N);
REP(i, M) {
if ((not lst[A[i].first].empty()) and lst[A[i].first].back().first == A[i].second) {
lst[A[i].first].back().second = true;
continue;
} else {
lst[A[i].first].emplace_back(A[i].second, true);
}
int f = A[i].first % A[i].second;
while (f < N) {
lst[f].emplace_back(A[i].second, false);
f += A[i].second;
if (f == A[i].first) f += A[i].second;
}
}
vector<int> size_r(N + 1);
REP(i, N) size_r[i + 1] = size_r[i] + (int)lst[i].size();
static array<pair<int, int>, V> pair_lr;
static array<int, V> par;
vector<vector<int>> chd(N);
vector<vector<int>> press(N);
REP(i, N) {
press[i].reserve(lst[i].size());
REP(j, (int)lst[i].size()) press[i].push_back(lst[i][j].first);
}
auto get_key = [&](int i, int w) { return lower_bound(ALL(press[i]), w) - press[i].begin(); };
REP(i, N) {
for (const auto &[w, c] : lst[i]) {
const int id = size_r[i] + get_key(i, w);
pair_lr[id] = {-1, -1};
par[id] = size_r[N] + i;
if (c) chd[i].push_back(id);
const int l = i - w;
if (l >= 0) {
const int id2 = size_r[l] + get_key(l, w);
pair_lr[id].first = id2;
pair_lr[id2].second = id;
}
}
}
static array<int, V> dist;
static array<bool, V> used;
fill(ALL(dist), inf);
fill(ALL(used), false);
dist[size_r[N] + A[S].first] = 0;
deque<int> deq;
deq.push_back(size_r[N] + A[S].first);
while (not deq.empty()) {
const int f = deq.front();
deq.pop_front();
if (used[f]) continue;
used[f] = true;
if (f >= size_r[N]) {
for (const int t : chd[f - size_r[N]]) {
if (chmin(dist[t], dist[f])) {
deq.push_front(t);
}
}
} else {
const auto &[l, r] = pair_lr[f];
if (l != -1 and chmin(dist[l], dist[f] + 1)) {
deq.push_back(l);
}
if (r != -1 and chmin(dist[r], dist[f] + 1)) {
deq.push_back(r);
}
const int pa = par[f];
if (chmin(dist[pa], dist[f])) {
deq.push_front(pa);
}
}
}
auto ans = dist[size_r[N] + A[T].first];
if (ans == inf) ans = -1;
cout << ans << endl;
}