oj.uz

Submission #564625

# Submission time Handle Problem Language Result Execution time Memory
564625 2022-05-19T12:14:38 Z Cyanmond Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 29 ms 51284 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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 = 10000000;
 
int main() {
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> A(M);
    REP(i, M) {
        cin >> A[i].first >> A[i].second;
        chmin(A[i].second, 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;
        }
    }
    vector<vector<pair<int, bool>>> 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].push_back({A[i].second, true});
        }
        int f = A[i].first % A[i].second;
        while (f < N) {
            lst[f].push_back({A[i].second, false});
            f += A[i].second;
            if (f == A[i].first) f += A[i].second;
        }
    }
 
    static array<int, 30010> size_r;
    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;
    static array<vector<int>, 30010> chd, press;
    REP(i, N) {
        press[i].reserve(lst[i].size());
        REP(j, (int)lst[i].size()) press[i].push_back(lst[i][j].first);
        press[i].erase(unique(ALL(press[i])), press[i].end());
    }

    auto size_r2=size_r;
 
    REP(i, N) {
        int id = size_r[i];
        for (const auto &[w, c] : lst[i]) {
            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_r2[l]++;
                pair_lr[id].first = id2;
                pair_lr[id2].second = id;
            }
            ++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 (f == size_r[N] + A[T].first) break;
        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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 50644 KB Output is correct
2 Correct 20 ms 50772 KB Output is correct
3 Correct 22 ms 50756 KB Output is correct
4 Correct 24 ms 50680 KB Output is correct
5 Correct 20 ms 50664 KB Output is correct
6 Correct 20 ms 50736 KB Output is correct
7 Correct 19 ms 50636 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 50744 KB Output is correct
2 Correct 19 ms 50740 KB Output is correct
3 Correct 19 ms 50772 KB Output is correct
4 Correct 20 ms 50676 KB Output is correct
5 Correct 21 ms 50768 KB Output is correct
6 Correct 20 ms 50644 KB Output is correct
7 Correct 21 ms 50772 KB Output is correct
8 Correct 20 ms 50772 KB Output is correct
9 Correct 20 ms 50768 KB Output is correct
10 Correct 20 ms 50840 KB Output is correct
11 Correct 20 ms 50932 KB Output is correct
12 Correct 20 ms 50724 KB Output is correct
13 Correct 21 ms 50720 KB Output is correct
14 Correct 20 ms 50900 KB Output is correct
15 Correct 20 ms 50904 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 50732 KB Output is correct
2 Correct 19 ms 50644 KB Output is correct
3 Correct 20 ms 50772 KB Output is correct
4 Correct 20 ms 50680 KB Output is correct
5 Correct 20 ms 50728 KB Output is correct
6 Correct 21 ms 50732 KB Output is correct
7 Correct 20 ms 50712 KB Output is correct
8 Correct 20 ms 50720 KB Output is correct
9 Correct 21 ms 50776 KB Output is correct
10 Correct 22 ms 50832 KB Output is correct
11 Correct 22 ms 50872 KB Output is correct
12 Correct 21 ms 50772 KB Output is correct
13 Correct 21 ms 50732 KB Output is correct
14 Correct 22 ms 50900 KB Output is correct
15 Correct 21 ms 50900 KB Output is correct
16 Correct 21 ms 50900 KB Output is correct
17 Correct 21 ms 51164 KB Output is correct
18 Correct 21 ms 51032 KB Output is correct
19 Correct 23 ms 51000 KB Output is correct
20 Correct 22 ms 51020 KB Output is correct
21 Correct 21 ms 50864 KB Output is correct
22 Correct 21 ms 50924 KB Output is correct
23 Correct 22 ms 51028 KB Output is correct
24 Correct 24 ms 51284 KB Output is correct
25 Incorrect 22 ms 51116 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 50772 KB Output is correct
2 Correct 19 ms 50676 KB Output is correct
3 Correct 21 ms 50772 KB Output is correct
4 Correct 21 ms 50772 KB Output is correct
5 Correct 21 ms 50752 KB Output is correct
6 Correct 22 ms 50772 KB Output is correct
7 Correct 21 ms 50644 KB Output is correct
8 Correct 20 ms 50712 KB Output is correct
9 Correct 20 ms 50772 KB Output is correct
10 Correct 20 ms 50796 KB Output is correct
11 Correct 21 ms 50900 KB Output is correct
12 Correct 20 ms 50680 KB Output is correct
13 Correct 20 ms 50760 KB Output is correct
14 Correct 21 ms 50900 KB Output is correct
15 Correct 23 ms 50996 KB Output is correct
16 Correct 20 ms 50900 KB Output is correct
17 Correct 23 ms 51144 KB Output is correct
18 Correct 21 ms 51060 KB Output is correct
19 Correct 21 ms 50956 KB Output is correct
20 Correct 22 ms 50940 KB Output is correct
21 Correct 21 ms 50764 KB Output is correct
22 Correct 21 ms 51008 KB Output is correct
23 Correct 21 ms 50960 KB Output is correct
24 Correct 22 ms 51284 KB Output is correct
25 Incorrect 22 ms 51104 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 50728 KB Output is correct
2 Correct 19 ms 50752 KB Output is correct
3 Correct 20 ms 50736 KB Output is correct
4 Correct 20 ms 50740 KB Output is correct
5 Correct 29 ms 50772 KB Output is correct
6 Correct 21 ms 50644 KB Output is correct
7 Correct 19 ms 50660 KB Output is correct
8 Correct 20 ms 50772 KB Output is correct
9 Correct 19 ms 50700 KB Output is correct
10 Correct 26 ms 50748 KB Output is correct
11 Correct 21 ms 50844 KB Output is correct
12 Correct 20 ms 50688 KB Output is correct
13 Correct 20 ms 50732 KB Output is correct
14 Correct 20 ms 50900 KB Output is correct
15 Correct 19 ms 50900 KB Output is correct
16 Correct 19 ms 50908 KB Output is correct
17 Correct 23 ms 51272 KB Output is correct
18 Correct 20 ms 51028 KB Output is correct
19 Correct 20 ms 51028 KB Output is correct
20 Correct 21 ms 51016 KB Output is correct
21 Correct 21 ms 50788 KB Output is correct
22 Correct 28 ms 51064 KB Output is correct
23 Correct 29 ms 50948 KB Output is correct
24 Correct 21 ms 51280 KB Output is correct
25 Incorrect 21 ms 51156 KB Output isn't correct
26 Halted 0 ms 0 KB -