oj.uz

Submission #707350

# Submission time Handle Problem Language Result Execution time Memory
707350 2023-03-08T20:07:27 Z Stickfish Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 63884 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <bitset>
using namespace std;

const int MAXN = 30100;
const int SQN = 100;
const int INF = 1e9 + 177013;
pair<int, int> dogs[MAXN];
vector<int> jlen[MAXN];

struct modmin {
    void resize(int n) {
        sz = n;
        for (int i = 0; i < n; ++i)
            active.insert(i);
        pivots = {{-INF, 10}, {INF, 10}};
    }

    void insert_pivot(int x, int vl) {
        auto it = active.lower_bound(x);
        if (it != active.end())
            best.erase({get_value(*it), *it});
        if (it != active.begin())
            best.erase({get_value(*prev(it)), *prev(it)});
        pivots.insert(lower_bound(pivots.begin(), pivots.end(), pair<int, int>{x, -1}), {x, vl});
        if (it != active.end())
            best.insert({get_value(*it), *it});
        if (it != active.begin())
            best.insert({get_value(*prev(it)), *prev(it)});
    }

    void deactivate(int x) {
        int vl = get_value(x);
        auto it = active.find(x);
        if (best.find({vl, x}) != best.end()) {
            best.erase({vl, x});
            if (next(it) != active.end())
                best.insert({get_value(*next(it)), *next(it)});
            if (it != active.begin())
                best.insert({get_value(*prev(it)), *prev(it)});
        }
        active.erase(it);
    }

    pair<int, int> get_min() {
        if (best.empty())
            return {INF, INF};
        return *best.begin();
    }
 private:
     int sz;
     set<pair<int, int>> pivots;
     set<int> active;
     set<pair<int, int>> best;

     int get_value(int x) {
         auto it = pivots.lower_bound({x, -1});
         return min(get_transit(it, x), get_transit(prev(it), x));
     }

     int get_transit(set<pair<int, int>>::iterator it, int x) {
         return abs(x - it->first) + it->second;
     }
};

bitset<MAXN> used;
int dist_long[MAXN];
modmin dist_short[SQN][MAXN / SQN];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> dogs[i].first >> dogs[i].second;
        jlen[dogs[i].first].push_back(dogs[i].second);
    }
    int s = dogs[0].first;
    int t = dogs[1].first;
    for (int i = 0; i < n; ++i)
        dist_long[i] = INF;
    dist_long[s] = 0;
    for (int d = 1; d < SQN; ++d) {
        for (int md = 0; md < n && md < d; ++md) {
            dist_short[d][md].resize((n - md - 1) / d + 1);
        }
    }
    set<pair<int, int>> rdist_short;
    int T = n;
    while (T--) {
        //cout << "A" << endl;
        pair<int, int> opt = {INF, INF};
        for (int i = 0; i < n; ++i) {
            if (!used[i])
                opt = min(opt, {dist_long[i], i});
        }
        if (rdist_short.size()) {
            opt = min(opt, *rdist_short.begin());
        }
        auto [dist, v] = opt;
        if (dist >= INF)
            break;
        dist_long[v] = dist;
        used[v] = 1;
        for (int d = 1; d < SQN; ++d) {
            int md = v % d;
            pair<int, int> cval = dist_short[d][md].get_min();
            cval.second = md + d * cval.second;
            rdist_short.erase(cval);

            dist_short[d][md].deactivate(v / d);

            pair<int, int> ncval = dist_short[d][md].get_min();
            ncval.second = md + d * ncval.second;
            rdist_short.insert(ncval);
        }
        for (auto p : jlen[v]) {
            if (p >= SQN) {
                for (int k = 1; p * k <= v; ++k)
                    dist_long[v - p * k] = min(dist_long[v - p * k], dist + k);
                for (int k = 1; v + p * k < n; ++k)
                    dist_long[v + p * k] = min(dist_long[v + p * k], dist + k);
            } else {
                int md = v % p;
                pair<int, int> cval = dist_short[p][md].get_min();
                cval.second = md + p * cval.second;
                rdist_short.erase(cval);

                dist_short[p][md].insert_pivot(v / p, dist);

                pair<int, int> ncval = dist_short[p][md].get_min();
                ncval.second = md + p * ncval.second;
                rdist_short.insert(ncval);
            }
        }
    }
    if (dist_long[t] >= INF)
        cout << "-1\n";
    else
        cout << dist_long[t] << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5460 KB Output is correct
2 Correct 2 ms 5460 KB Output is correct
3 Correct 3 ms 5588 KB Output is correct
4 Correct 4 ms 5588 KB Output is correct
5 Correct 3 ms 5588 KB Output is correct
6 Correct 3 ms 5556 KB Output is correct
7 Correct 5 ms 5588 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5588 KB Output is correct
2 Correct 3 ms 5536 KB Output is correct
3 Correct 3 ms 5588 KB Output is correct
4 Correct 3 ms 5588 KB Output is correct
5 Correct 3 ms 5548 KB Output is correct
6 Correct 3 ms 5588 KB Output is correct
7 Correct 3 ms 5588 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Correct 5 ms 6100 KB Output is correct
10 Correct 7 ms 6356 KB Output is correct
11 Correct 10 ms 6492 KB Output is correct
12 Correct 9 ms 6356 KB Output is correct
13 Correct 10 ms 6356 KB Output is correct
14 Correct 8 ms 6484 KB Output is correct
15 Correct 8 ms 6484 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5460 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 3 ms 5544 KB Output is correct
4 Correct 3 ms 5588 KB Output is correct
5 Correct 3 ms 5588 KB Output is correct
6 Correct 3 ms 5588 KB Output is correct
7 Correct 3 ms 5588 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Correct 5 ms 6100 KB Output is correct
10 Correct 7 ms 6356 KB Output is correct
11 Correct 8 ms 6484 KB Output is correct
12 Correct 7 ms 6356 KB Output is correct
13 Correct 9 ms 6456 KB Output is correct
14 Correct 7 ms 6484 KB Output is correct
15 Correct 7 ms 6484 KB Output is correct
16 Correct 5 ms 6868 KB Output is correct
17 Correct 41 ms 9428 KB Output is correct
18 Correct 19 ms 14124 KB Output is correct
19 Correct 23 ms 15356 KB Output is correct
20 Correct 152 ms 15348 KB Output is correct
21 Correct 6 ms 7764 KB Output is correct
22 Correct 19 ms 14304 KB Output is correct
23 Correct 109 ms 13464 KB Output is correct
24 Correct 137 ms 14868 KB Output is correct
25 Correct 139 ms 15328 KB Output is correct
26 Correct 126 ms 15316 KB Output is correct
27 Correct 121 ms 15316 KB Output is correct
28 Correct 140 ms 15356 KB Output is correct
29 Correct 132 ms 15296 KB Output is correct
30 Correct 129 ms 15188 KB Output is correct
31 Correct 138 ms 15292 KB Output is correct
32 Correct 130 ms 15300 KB Output is correct
33 Correct 127 ms 15356 KB Output is correct
34 Correct 127 ms 15356 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5588 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 3 ms 5632 KB Output is correct
4 Correct 3 ms 5588 KB Output is correct
5 Correct 3 ms 5588 KB Output is correct
6 Correct 3 ms 5588 KB Output is correct
7 Correct 3 ms 5588 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Correct 6 ms 6100 KB Output is correct
10 Correct 8 ms 6456 KB Output is correct
11 Correct 8 ms 6484 KB Output is correct
12 Correct 8 ms 6356 KB Output is correct
13 Correct 11 ms 6484 KB Output is correct
14 Correct 8 ms 6484 KB Output is correct
15 Correct 8 ms 6484 KB Output is correct
16 Correct 5 ms 6856 KB Output is correct
17 Correct 41 ms 9428 KB Output is correct
18 Correct 19 ms 14144 KB Output is correct
19 Correct 22 ms 15216 KB Output is correct
20 Correct 152 ms 15336 KB Output is correct
21 Correct 6 ms 7764 KB Output is correct
22 Correct 18 ms 14184 KB Output is correct
23 Correct 109 ms 13436 KB Output is correct
24 Correct 140 ms 14804 KB Output is correct
25 Correct 143 ms 15328 KB Output is correct
26 Correct 124 ms 15308 KB Output is correct
27 Correct 123 ms 15296 KB Output is correct
28 Correct 160 ms 15348 KB Output is correct
29 Correct 128 ms 15296 KB Output is correct
30 Correct 125 ms 15272 KB Output is correct
31 Correct 135 ms 15188 KB Output is correct
32 Correct 138 ms 15280 KB Output is correct
33 Correct 133 ms 15356 KB Output is correct
34 Correct 125 ms 15316 KB Output is correct
35 Correct 93 ms 13016 KB Output is correct
36 Correct 65 ms 11092 KB Output is correct
37 Correct 144 ms 15276 KB Output is correct
38 Correct 155 ms 15700 KB Output is correct
39 Correct 149 ms 15712 KB Output is correct
40 Correct 145 ms 15712 KB Output is correct
41 Correct 162 ms 15704 KB Output is correct
42 Correct 158 ms 15572 KB Output is correct
43 Correct 140 ms 15632 KB Output is correct
44 Correct 691 ms 15676 KB Output is correct
45 Correct 146 ms 15828 KB Output is correct
46 Correct 129 ms 15696 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5588 KB Output is correct
2 Correct 2 ms 5460 KB Output is correct
3 Correct 3 ms 5588 KB Output is correct
4 Correct 3 ms 5588 KB Output is correct
5 Correct 3 ms 5588 KB Output is correct
6 Correct 4 ms 5588 KB Output is correct
7 Correct 3 ms 5588 KB Output is correct
8 Correct 4 ms 5844 KB Output is correct
9 Correct 5 ms 6184 KB Output is correct
10 Correct 8 ms 6460 KB Output is correct
11 Correct 8 ms 6484 KB Output is correct
12 Correct 8 ms 6476 KB Output is correct
13 Correct 9 ms 6356 KB Output is correct
14 Correct 8 ms 6484 KB Output is correct
15 Correct 7 ms 6528 KB Output is correct
16 Correct 5 ms 6868 KB Output is correct
17 Correct 44 ms 9356 KB Output is correct
18 Correct 19 ms 14036 KB Output is correct
19 Correct 23 ms 15300 KB Output is correct
20 Correct 153 ms 15364 KB Output is correct
21 Correct 6 ms 7764 KB Output is correct
22 Correct 19 ms 14188 KB Output is correct
23 Correct 107 ms 13440 KB Output is correct
24 Correct 152 ms 14796 KB Output is correct
25 Correct 143 ms 15316 KB Output is correct
26 Correct 119 ms 15208 KB Output is correct
27 Correct 126 ms 15296 KB Output is correct
28 Correct 141 ms 15416 KB Output is correct
29 Correct 134 ms 15296 KB Output is correct
30 Correct 135 ms 15272 KB Output is correct
31 Correct 139 ms 15284 KB Output is correct
32 Correct 133 ms 15248 KB Output is correct
33 Correct 124 ms 15352 KB Output is correct
34 Correct 125 ms 15348 KB Output is correct
35 Correct 108 ms 13028 KB Output is correct
36 Correct 72 ms 11124 KB Output is correct
37 Correct 159 ms 15272 KB Output is correct
38 Correct 212 ms 15700 KB Output is correct
39 Correct 174 ms 15708 KB Output is correct
40 Correct 156 ms 15708 KB Output is correct
41 Correct 205 ms 15700 KB Output is correct
42 Correct 133 ms 15628 KB Output is correct
43 Correct 141 ms 15628 KB Output is correct
44 Correct 785 ms 15680 KB Output is correct
45 Correct 137 ms 15804 KB Output is correct
46 Correct 139 ms 15804 KB Output is correct
47 Execution timed out 1080 ms 63884 KB Time limit exceeded
48 Halted 0 ms 0 KB -