oj.uz

Submission #564637

# Submission time Handle Problem Language Result Execution time Memory
564637 2022-05-19T12:22:55 Z Cyanmond Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 956 ms 227564 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) {
            if (f == A[i].first) {
                f += A[i].second;
                continue;
            }
            lst[f].push_back({A[i].second, false});
            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);
    }
 
    auto get_key = [&](int i, int w) { return lower_bound(ALL(press[i]), w) - press[i].begin(); };
    vector<int> cnt(N);
    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_r[l] + cnt[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;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:78:10: warning: variable 'get_key' set but not used [-Wunused-but-set-variable]
   78 |     auto get_key = [&](int i, int w) { return lower_bound(ALL(press[i]), w) - press[i].begin(); };
      |          ^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 50644 KB Output is correct
2 Correct 20 ms 50644 KB Output is correct
3 Correct 21 ms 50532 KB Output is correct
4 Correct 23 ms 50600 KB Output is correct
5 Correct 23 ms 50640 KB Output is correct
6 Correct 20 ms 50580 KB Output is correct
7 Correct 22 ms 50580 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 50644 KB Output is correct
2 Correct 24 ms 50604 KB Output is correct
3 Correct 20 ms 50540 KB Output is correct
4 Correct 23 ms 50588 KB Output is correct
5 Correct 25 ms 50644 KB Output is correct
6 Correct 19 ms 50652 KB Output is correct
7 Correct 21 ms 50632 KB Output is correct
8 Correct 23 ms 50644 KB Output is correct
9 Correct 22 ms 50644 KB Output is correct
10 Correct 21 ms 50676 KB Output is correct
11 Correct 21 ms 50772 KB Output is correct
12 Correct 19 ms 50656 KB Output is correct
13 Correct 21 ms 50612 KB Output is correct
14 Correct 20 ms 50772 KB Output is correct
15 Correct 20 ms 50784 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 50568 KB Output is correct
2 Correct 21 ms 50632 KB Output is correct
3 Correct 20 ms 50512 KB Output is correct
4 Correct 21 ms 50516 KB Output is correct
5 Correct 20 ms 50580 KB Output is correct
6 Correct 20 ms 50644 KB Output is correct
7 Correct 20 ms 50644 KB Output is correct
8 Correct 19 ms 50644 KB Output is correct
9 Correct 20 ms 50636 KB Output is correct
10 Correct 20 ms 50640 KB Output is correct
11 Correct 21 ms 50744 KB Output is correct
12 Correct 23 ms 50644 KB Output is correct
13 Correct 21 ms 50580 KB Output is correct
14 Correct 24 ms 50820 KB Output is correct
15 Correct 24 ms 50764 KB Output is correct
16 Correct 23 ms 50680 KB Output is correct
17 Correct 25 ms 51100 KB Output is correct
18 Correct 24 ms 50864 KB Output is correct
19 Correct 20 ms 50900 KB Output is correct
20 Correct 22 ms 50900 KB Output is correct
21 Correct 20 ms 50644 KB Output is correct
22 Correct 20 ms 50848 KB Output is correct
23 Correct 20 ms 50892 KB Output is correct
24 Correct 26 ms 51116 KB Output is correct
25 Correct 25 ms 50908 KB Output is correct
26 Correct 27 ms 50872 KB Output is correct
27 Correct 25 ms 50960 KB Output is correct
28 Correct 23 ms 51452 KB Output is correct
29 Correct 28 ms 52172 KB Output is correct
30 Correct 25 ms 51284 KB Output is correct
31 Correct 22 ms 51700 KB Output is correct
32 Correct 21 ms 51412 KB Output is correct
33 Correct 38 ms 53700 KB Output is correct
34 Correct 29 ms 53716 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 50636 KB Output is correct
2 Correct 28 ms 50620 KB Output is correct
3 Correct 29 ms 50568 KB Output is correct
4 Correct 25 ms 50564 KB Output is correct
5 Correct 22 ms 50644 KB Output is correct
6 Correct 21 ms 50536 KB Output is correct
7 Correct 21 ms 50564 KB Output is correct
8 Correct 28 ms 50548 KB Output is correct
9 Correct 26 ms 50564 KB Output is correct
10 Correct 21 ms 50644 KB Output is correct
11 Correct 21 ms 50772 KB Output is correct
12 Correct 23 ms 50592 KB Output is correct
13 Correct 21 ms 50644 KB Output is correct
14 Correct 22 ms 50780 KB Output is correct
15 Correct 21 ms 50772 KB Output is correct
16 Correct 21 ms 50756 KB Output is correct
17 Correct 22 ms 51028 KB Output is correct
18 Correct 28 ms 50892 KB Output is correct
19 Correct 21 ms 50892 KB Output is correct
20 Correct 21 ms 50920 KB Output is correct
21 Correct 21 ms 50636 KB Output is correct
22 Correct 27 ms 50900 KB Output is correct
23 Correct 28 ms 50916 KB Output is correct
24 Correct 29 ms 51156 KB Output is correct
25 Correct 26 ms 50976 KB Output is correct
26 Correct 21 ms 50956 KB Output is correct
27 Correct 21 ms 50868 KB Output is correct
28 Correct 25 ms 51420 KB Output is correct
29 Correct 29 ms 52156 KB Output is correct
30 Correct 25 ms 51280 KB Output is correct
31 Correct 27 ms 51732 KB Output is correct
32 Correct 22 ms 51380 KB Output is correct
33 Correct 28 ms 53612 KB Output is correct
34 Correct 31 ms 53704 KB Output is correct
35 Correct 40 ms 53844 KB Output is correct
36 Correct 24 ms 51184 KB Output is correct
37 Correct 41 ms 55788 KB Output is correct
38 Correct 45 ms 55712 KB Output is correct
39 Correct 43 ms 55720 KB Output is correct
40 Correct 43 ms 55652 KB Output is correct
41 Correct 44 ms 55764 KB Output is correct
42 Correct 32 ms 51204 KB Output is correct
43 Correct 31 ms 51124 KB Output is correct
44 Correct 31 ms 51104 KB Output is correct
45 Correct 64 ms 62804 KB Output is correct
46 Correct 54 ms 62844 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 50644 KB Output is correct
2 Correct 20 ms 50544 KB Output is correct
3 Correct 19 ms 50644 KB Output is correct
4 Correct 24 ms 50656 KB Output is correct
5 Correct 20 ms 50644 KB Output is correct
6 Correct 23 ms 50620 KB Output is correct
7 Correct 24 ms 50584 KB Output is correct
8 Correct 23 ms 50612 KB Output is correct
9 Correct 22 ms 50644 KB Output is correct
10 Correct 21 ms 50684 KB Output is correct
11 Correct 21 ms 50772 KB Output is correct
12 Correct 21 ms 50644 KB Output is correct
13 Correct 21 ms 50632 KB Output is correct
14 Correct 21 ms 50772 KB Output is correct
15 Correct 21 ms 50808 KB Output is correct
16 Correct 26 ms 50728 KB Output is correct
17 Correct 26 ms 51112 KB Output is correct
18 Correct 25 ms 50964 KB Output is correct
19 Correct 21 ms 50900 KB Output is correct
20 Correct 27 ms 50904 KB Output is correct
21 Correct 21 ms 50732 KB Output is correct
22 Correct 21 ms 50832 KB Output is correct
23 Correct 21 ms 50908 KB Output is correct
24 Correct 21 ms 51156 KB Output is correct
25 Correct 22 ms 50932 KB Output is correct
26 Correct 21 ms 50888 KB Output is correct
27 Correct 25 ms 50936 KB Output is correct
28 Correct 22 ms 51412 KB Output is correct
29 Correct 23 ms 52212 KB Output is correct
30 Correct 27 ms 51284 KB Output is correct
31 Correct 22 ms 51748 KB Output is correct
32 Correct 21 ms 51400 KB Output is correct
33 Correct 30 ms 53656 KB Output is correct
34 Correct 27 ms 53684 KB Output is correct
35 Correct 39 ms 53824 KB Output is correct
36 Correct 22 ms 51196 KB Output is correct
37 Correct 38 ms 55756 KB Output is correct
38 Correct 44 ms 55692 KB Output is correct
39 Correct 42 ms 55672 KB Output is correct
40 Correct 43 ms 55672 KB Output is correct
41 Correct 44 ms 55716 KB Output is correct
42 Correct 31 ms 51156 KB Output is correct
43 Correct 33 ms 51104 KB Output is correct
44 Correct 32 ms 51096 KB Output is correct
45 Correct 60 ms 62796 KB Output is correct
46 Correct 52 ms 62880 KB Output is correct
47 Correct 74 ms 71192 KB Output is correct
48 Correct 50 ms 58828 KB Output is correct
49 Correct 46 ms 56524 KB Output is correct
50 Correct 43 ms 56672 KB Output is correct
51 Correct 77 ms 61672 KB Output is correct
52 Correct 77 ms 62492 KB Output is correct
53 Correct 50 ms 55808 KB Output is correct
54 Correct 25 ms 53776 KB Output is correct
55 Correct 26 ms 54100 KB Output is correct
56 Correct 39 ms 54988 KB Output is correct
57 Correct 54 ms 63180 KB Output is correct
58 Correct 37 ms 54736 KB Output is correct
59 Correct 50 ms 55328 KB Output is correct
60 Correct 46 ms 55944 KB Output is correct
61 Correct 44 ms 55580 KB Output is correct
62 Correct 96 ms 66724 KB Output is correct
63 Correct 406 ms 118388 KB Output is correct
64 Correct 473 ms 127588 KB Output is correct
65 Correct 656 ms 170448 KB Output is correct
66 Correct 956 ms 227320 KB Output is correct
67 Correct 611 ms 227564 KB Output is correct