oj.uz

Submission #564045

# Submission time Handle Problem Language Result Execution time Memory
564045 2022-05-18T13:30:45 Z Cyanmond Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 222816 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;
    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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 74316 KB Output is correct
2 Correct 32 ms 74284 KB Output is correct
3 Correct 32 ms 74272 KB Output is correct
4 Correct 31 ms 74360 KB Output is correct
5 Correct 32 ms 74304 KB Output is correct
6 Correct 34 ms 74444 KB Output is correct
7 Correct 34 ms 74372 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 74356 KB Output is correct
2 Correct 31 ms 74312 KB Output is correct
3 Correct 32 ms 74264 KB Output is correct
4 Correct 37 ms 74332 KB Output is correct
5 Correct 34 ms 74332 KB Output is correct
6 Correct 32 ms 74324 KB Output is correct
7 Correct 32 ms 74344 KB Output is correct
8 Correct 32 ms 74316 KB Output is correct
9 Correct 32 ms 74372 KB Output is correct
10 Correct 32 ms 74316 KB Output is correct
11 Correct 33 ms 74428 KB Output is correct
12 Correct 33 ms 74360 KB Output is correct
13 Correct 32 ms 74308 KB Output is correct
14 Correct 35 ms 74600 KB Output is correct
15 Correct 38 ms 74572 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 74324 KB Output is correct
2 Correct 32 ms 74372 KB Output is correct
3 Correct 32 ms 74284 KB Output is correct
4 Correct 32 ms 74388 KB Output is correct
5 Correct 34 ms 74408 KB Output is correct
6 Correct 33 ms 74356 KB Output is correct
7 Correct 32 ms 74340 KB Output is correct
8 Correct 32 ms 74320 KB Output is correct
9 Correct 32 ms 74280 KB Output is correct
10 Correct 32 ms 74320 KB Output is correct
11 Correct 32 ms 74432 KB Output is correct
12 Correct 37 ms 74292 KB Output is correct
13 Correct 37 ms 74312 KB Output is correct
14 Correct 34 ms 74552 KB Output is correct
15 Correct 34 ms 74568 KB Output is correct
16 Correct 33 ms 74500 KB Output is correct
17 Correct 35 ms 74796 KB Output is correct
18 Correct 33 ms 74636 KB Output is correct
19 Correct 34 ms 74580 KB Output is correct
20 Correct 35 ms 74592 KB Output is correct
21 Correct 33 ms 74420 KB Output is correct
22 Correct 33 ms 74660 KB Output is correct
23 Correct 37 ms 74704 KB Output is correct
24 Correct 36 ms 74764 KB Output is correct
25 Correct 34 ms 74668 KB Output is correct
26 Correct 34 ms 74700 KB Output is correct
27 Correct 33 ms 74636 KB Output is correct
28 Correct 36 ms 75032 KB Output is correct
29 Correct 38 ms 75772 KB Output is correct
30 Correct 35 ms 74828 KB Output is correct
31 Correct 35 ms 75204 KB Output is correct
32 Correct 34 ms 75024 KB Output is correct
33 Correct 46 ms 76972 KB Output is correct
34 Correct 49 ms 76984 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 74296 KB Output is correct
2 Correct 36 ms 74260 KB Output is correct
3 Correct 33 ms 74304 KB Output is correct
4 Correct 33 ms 74284 KB Output is correct
5 Correct 32 ms 74312 KB Output is correct
6 Correct 33 ms 74336 KB Output is correct
7 Correct 35 ms 74340 KB Output is correct
8 Correct 32 ms 74340 KB Output is correct
9 Correct 35 ms 74272 KB Output is correct
10 Correct 33 ms 74372 KB Output is correct
11 Correct 33 ms 74444 KB Output is correct
12 Correct 34 ms 74384 KB Output is correct
13 Correct 33 ms 74400 KB Output is correct
14 Correct 33 ms 74532 KB Output is correct
15 Correct 34 ms 74592 KB Output is correct
16 Correct 33 ms 74452 KB Output is correct
17 Correct 37 ms 74700 KB Output is correct
18 Correct 34 ms 74628 KB Output is correct
19 Correct 36 ms 74616 KB Output is correct
20 Correct 33 ms 74636 KB Output is correct
21 Correct 32 ms 74468 KB Output is correct
22 Correct 33 ms 74640 KB Output is correct
23 Correct 33 ms 74576 KB Output is correct
24 Correct 35 ms 74836 KB Output is correct
25 Correct 35 ms 74700 KB Output is correct
26 Correct 35 ms 74760 KB Output is correct
27 Correct 34 ms 74708 KB Output is correct
28 Correct 36 ms 75084 KB Output is correct
29 Correct 39 ms 75724 KB Output is correct
30 Correct 38 ms 74836 KB Output is correct
31 Correct 36 ms 75232 KB Output is correct
32 Correct 38 ms 74976 KB Output is correct
33 Correct 46 ms 77004 KB Output is correct
34 Correct 46 ms 76992 KB Output is correct
35 Correct 57 ms 77132 KB Output is correct
36 Correct 36 ms 74820 KB Output is correct
37 Correct 64 ms 78588 KB Output is correct
38 Correct 68 ms 78696 KB Output is correct
39 Correct 68 ms 78620 KB Output is correct
40 Correct 69 ms 78660 KB Output is correct
41 Correct 68 ms 78676 KB Output is correct
42 Correct 47 ms 74836 KB Output is correct
43 Correct 45 ms 74824 KB Output is correct
44 Correct 44 ms 74760 KB Output is correct
45 Correct 109 ms 85148 KB Output is correct
46 Correct 110 ms 85124 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 74280 KB Output is correct
2 Correct 32 ms 74376 KB Output is correct
3 Correct 32 ms 74340 KB Output is correct
4 Correct 32 ms 74372 KB Output is correct
5 Correct 39 ms 74304 KB Output is correct
6 Correct 32 ms 74464 KB Output is correct
7 Correct 32 ms 74280 KB Output is correct
8 Correct 34 ms 74332 KB Output is correct
9 Correct 33 ms 74300 KB Output is correct
10 Correct 32 ms 74316 KB Output is correct
11 Correct 33 ms 74444 KB Output is correct
12 Correct 33 ms 74364 KB Output is correct
13 Correct 34 ms 74368 KB Output is correct
14 Correct 34 ms 74548 KB Output is correct
15 Correct 36 ms 74480 KB Output is correct
16 Correct 34 ms 74492 KB Output is correct
17 Correct 35 ms 74680 KB Output is correct
18 Correct 33 ms 74672 KB Output is correct
19 Correct 33 ms 74588 KB Output is correct
20 Correct 34 ms 74680 KB Output is correct
21 Correct 33 ms 74456 KB Output is correct
22 Correct 33 ms 74656 KB Output is correct
23 Correct 33 ms 74652 KB Output is correct
24 Correct 35 ms 74836 KB Output is correct
25 Correct 36 ms 74752 KB Output is correct
26 Correct 51 ms 74700 KB Output is correct
27 Correct 37 ms 74608 KB Output is correct
28 Correct 36 ms 75068 KB Output is correct
29 Correct 38 ms 75708 KB Output is correct
30 Correct 34 ms 74848 KB Output is correct
31 Correct 39 ms 75300 KB Output is correct
32 Correct 37 ms 75064 KB Output is correct
33 Correct 46 ms 76992 KB Output is correct
34 Correct 46 ms 77016 KB Output is correct
35 Correct 57 ms 77072 KB Output is correct
36 Correct 37 ms 74932 KB Output is correct
37 Correct 65 ms 78620 KB Output is correct
38 Correct 70 ms 78660 KB Output is correct
39 Correct 72 ms 78728 KB Output is correct
40 Correct 69 ms 78624 KB Output is correct
41 Correct 69 ms 78668 KB Output is correct
42 Correct 43 ms 74784 KB Output is correct
43 Correct 45 ms 74824 KB Output is correct
44 Correct 58 ms 74700 KB Output is correct
45 Correct 106 ms 85188 KB Output is correct
46 Correct 106 ms 85136 KB Output is correct
47 Correct 187 ms 91448 KB Output is correct
48 Correct 71 ms 82032 KB Output is correct
49 Correct 63 ms 80304 KB Output is correct
50 Correct 62 ms 80304 KB Output is correct
51 Correct 111 ms 84548 KB Output is correct
52 Correct 112 ms 85144 KB Output is correct
53 Correct 65 ms 80080 KB Output is correct
54 Correct 37 ms 78120 KB Output is correct
55 Correct 42 ms 78364 KB Output is correct
56 Correct 53 ms 79132 KB Output is correct
57 Correct 87 ms 85752 KB Output is correct
58 Correct 49 ms 78760 KB Output is correct
59 Correct 57 ms 79104 KB Output is correct
60 Correct 59 ms 79564 KB Output is correct
61 Correct 58 ms 79392 KB Output is correct
62 Correct 125 ms 88880 KB Output is correct
63 Correct 549 ms 128520 KB Output is correct
64 Correct 649 ms 137612 KB Output is correct
65 Correct 927 ms 168620 KB Output is correct
66 Execution timed out 1109 ms 222816 KB Time limit exceeded
67 Halted 0 ms 0 KB -