oj.uz

Submission #564478

# Submission time Handle Problem Language Result Execution time Memory
564478 2022-05-19T09:33:56 Z Cyanmond Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 168452 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 = 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;
        }
    }
    vector<vector<pair<short, 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;
        }
    }
 
    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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 73584 KB Output is correct
2 Correct 28 ms 73672 KB Output is correct
3 Correct 28 ms 73684 KB Output is correct
4 Correct 32 ms 73616 KB Output is correct
5 Correct 31 ms 73604 KB Output is correct
6 Correct 30 ms 73592 KB Output is correct
7 Correct 34 ms 73676 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 73576 KB Output is correct
2 Correct 31 ms 73640 KB Output is correct
3 Correct 30 ms 73668 KB Output is correct
4 Correct 29 ms 73676 KB Output is correct
5 Correct 29 ms 73676 KB Output is correct
6 Correct 32 ms 73584 KB Output is correct
7 Correct 29 ms 73584 KB Output is correct
8 Correct 30 ms 73596 KB Output is correct
9 Correct 36 ms 73676 KB Output is correct
10 Correct 32 ms 73676 KB Output is correct
11 Correct 31 ms 73724 KB Output is correct
12 Correct 30 ms 73656 KB Output is correct
13 Correct 29 ms 73620 KB Output is correct
14 Correct 31 ms 73832 KB Output is correct
15 Correct 30 ms 73812 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 73628 KB Output is correct
2 Correct 36 ms 73676 KB Output is correct
3 Correct 46 ms 73628 KB Output is correct
4 Correct 30 ms 73676 KB Output is correct
5 Correct 29 ms 73676 KB Output is correct
6 Correct 29 ms 73676 KB Output is correct
7 Correct 29 ms 73796 KB Output is correct
8 Correct 30 ms 73684 KB Output is correct
9 Correct 32 ms 73636 KB Output is correct
10 Correct 36 ms 73708 KB Output is correct
11 Correct 38 ms 73772 KB Output is correct
12 Correct 33 ms 73796 KB Output is correct
13 Correct 33 ms 73684 KB Output is correct
14 Correct 30 ms 73896 KB Output is correct
15 Correct 31 ms 73860 KB Output is correct
16 Correct 32 ms 73736 KB Output is correct
17 Correct 36 ms 74032 KB Output is correct
18 Correct 30 ms 73932 KB Output is correct
19 Correct 37 ms 73940 KB Output is correct
20 Correct 32 ms 74072 KB Output is correct
21 Correct 31 ms 73684 KB Output is correct
22 Correct 34 ms 73948 KB Output is correct
23 Correct 32 ms 73936 KB Output is correct
24 Correct 32 ms 74168 KB Output is correct
25 Correct 33 ms 74024 KB Output is correct
26 Correct 32 ms 74068 KB Output is correct
27 Correct 32 ms 74068 KB Output is correct
28 Correct 36 ms 74388 KB Output is correct
29 Correct 41 ms 75020 KB Output is correct
30 Correct 42 ms 74188 KB Output is correct
31 Correct 33 ms 74604 KB Output is correct
32 Correct 33 ms 74316 KB Output is correct
33 Correct 43 ms 76364 KB Output is correct
34 Correct 44 ms 76360 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 73660 KB Output is correct
2 Correct 30 ms 73684 KB Output is correct
3 Correct 29 ms 73592 KB Output is correct
4 Correct 33 ms 73632 KB Output is correct
5 Correct 30 ms 73684 KB Output is correct
6 Correct 38 ms 73684 KB Output is correct
7 Correct 38 ms 73680 KB Output is correct
8 Correct 28 ms 73648 KB Output is correct
9 Correct 30 ms 73620 KB Output is correct
10 Correct 30 ms 73676 KB Output is correct
11 Correct 30 ms 73804 KB Output is correct
12 Correct 30 ms 73648 KB Output is correct
13 Correct 31 ms 73640 KB Output is correct
14 Correct 34 ms 73872 KB Output is correct
15 Correct 33 ms 73816 KB Output is correct
16 Correct 31 ms 73684 KB Output is correct
17 Correct 31 ms 73992 KB Output is correct
18 Correct 31 ms 74008 KB Output is correct
19 Correct 32 ms 73932 KB Output is correct
20 Correct 31 ms 73968 KB Output is correct
21 Correct 33 ms 73808 KB Output is correct
22 Correct 38 ms 73944 KB Output is correct
23 Correct 34 ms 74060 KB Output is correct
24 Correct 43 ms 74216 KB Output is correct
25 Correct 38 ms 74100 KB Output is correct
26 Correct 32 ms 74108 KB Output is correct
27 Correct 32 ms 74060 KB Output is correct
28 Correct 36 ms 74348 KB Output is correct
29 Correct 40 ms 75036 KB Output is correct
30 Correct 37 ms 74316 KB Output is correct
31 Correct 39 ms 74656 KB Output is correct
32 Correct 38 ms 74308 KB Output is correct
33 Correct 44 ms 76344 KB Output is correct
34 Correct 45 ms 76288 KB Output is correct
35 Correct 60 ms 76420 KB Output is correct
36 Correct 35 ms 74196 KB Output is correct
37 Correct 66 ms 77936 KB Output is correct
38 Correct 67 ms 78008 KB Output is correct
39 Correct 71 ms 78056 KB Output is correct
40 Correct 71 ms 78076 KB Output is correct
41 Correct 70 ms 78044 KB Output is correct
42 Correct 42 ms 74088 KB Output is correct
43 Correct 44 ms 74060 KB Output is correct
44 Correct 43 ms 74068 KB Output is correct
45 Correct 114 ms 84488 KB Output is correct
46 Correct 111 ms 84488 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 73676 KB Output is correct
2 Correct 29 ms 73676 KB Output is correct
3 Correct 37 ms 73616 KB Output is correct
4 Correct 31 ms 73576 KB Output is correct
5 Correct 29 ms 73676 KB Output is correct
6 Correct 31 ms 73604 KB Output is correct
7 Correct 31 ms 73672 KB Output is correct
8 Correct 31 ms 73652 KB Output is correct
9 Correct 37 ms 73636 KB Output is correct
10 Correct 37 ms 73620 KB Output is correct
11 Correct 32 ms 73804 KB Output is correct
12 Correct 36 ms 73604 KB Output is correct
13 Correct 30 ms 73680 KB Output is correct
14 Correct 30 ms 73860 KB Output is correct
15 Correct 31 ms 73864 KB Output is correct
16 Correct 35 ms 73736 KB Output is correct
17 Correct 40 ms 74060 KB Output is correct
18 Correct 38 ms 73980 KB Output is correct
19 Correct 33 ms 73928 KB Output is correct
20 Correct 31 ms 74020 KB Output is correct
21 Correct 30 ms 73740 KB Output is correct
22 Correct 31 ms 73940 KB Output is correct
23 Correct 38 ms 73984 KB Output is correct
24 Correct 33 ms 74196 KB Output is correct
25 Correct 33 ms 74032 KB Output is correct
26 Correct 32 ms 74060 KB Output is correct
27 Correct 31 ms 73992 KB Output is correct
28 Correct 35 ms 74384 KB Output is correct
29 Correct 35 ms 75112 KB Output is correct
30 Correct 34 ms 74256 KB Output is correct
31 Correct 34 ms 74616 KB Output is correct
32 Correct 32 ms 74316 KB Output is correct
33 Correct 45 ms 76372 KB Output is correct
34 Correct 43 ms 76332 KB Output is correct
35 Correct 56 ms 76408 KB Output is correct
36 Correct 32 ms 74180 KB Output is correct
37 Correct 66 ms 77916 KB Output is correct
38 Correct 73 ms 78032 KB Output is correct
39 Correct 73 ms 78000 KB Output is correct
40 Correct 72 ms 77968 KB Output is correct
41 Correct 71 ms 77992 KB Output is correct
42 Correct 46 ms 74136 KB Output is correct
43 Correct 44 ms 74148 KB Output is correct
44 Correct 38 ms 74064 KB Output is correct
45 Correct 112 ms 84576 KB Output is correct
46 Correct 125 ms 84504 KB Output is correct
47 Correct 193 ms 91044 KB Output is correct
48 Correct 85 ms 81876 KB Output is correct
49 Correct 67 ms 80192 KB Output is correct
50 Correct 72 ms 80180 KB Output is correct
51 Correct 121 ms 84556 KB Output is correct
52 Correct 114 ms 85144 KB Output is correct
53 Correct 66 ms 80148 KB Output is correct
54 Correct 33 ms 78104 KB Output is correct
55 Correct 38 ms 78372 KB Output is correct
56 Correct 55 ms 79156 KB Output is correct
57 Correct 94 ms 85760 KB Output is correct
58 Correct 50 ms 78668 KB Output is correct
59 Correct 54 ms 79108 KB Output is correct
60 Correct 61 ms 79552 KB Output is correct
61 Correct 55 ms 79384 KB Output is correct
62 Correct 144 ms 88876 KB Output is correct
63 Correct 635 ms 128388 KB Output is correct
64 Correct 758 ms 137616 KB Output is correct
65 Execution timed out 1002 ms 168452 KB Time limit exceeded
66 Halted 0 ms 0 KB -