oj.uz

Submission #707339

# Submission time Handle Problem Language Result Execution time Memory
707339 2023-03-08T19:47:08 Z Stickfish Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 1000 ms 6968 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <bitset>
using namespace std;

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

struct modmin {
    void resize(int n) {
        sz = n;
        used.resize(sz);
        pivots = {{-INF, 10}, {INF, 10}};
    }

    void insert_pivot(int x, int vl) {
        pivots.insert(lower_bound(pivots.begin(), pivots.end(), pair<int, int>{x, -1}), {x, vl});
    }

    void deactivate(int x) {
        used[x] = 1;
    }

    pair<int, int> get_min() {
        int i = 0;
        pair<int, int> ans = {INF, INF};
        for (int x = 0; x < sz; ++x) {
            if (pivots[i].first == INF)
                break;
            if (x - pivots[i].first + pivots[i].second > pivots[i + 1].first - x + pivots[i + 1].second)
                ++i;
            if (!used[x])
                ans = min(ans, {abs(x - pivots[i].first) + pivots[i].second, x});
        }
        return ans;
    }
 //private:
     int sz;
     vector<pair<int, int>> pivots;
     vector<bool> used;
};

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

signed main() {
    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;
                //cout << "! " << p << ' ' << md << endl;
                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 2 ms 3924 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3924 KB Output is correct
4 Correct 2 ms 3924 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 3 ms 3924 KB Output is correct
7 Correct 2 ms 4052 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3924 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3924 KB Output is correct
4 Correct 3 ms 3924 KB Output is correct
5 Correct 3 ms 3924 KB Output is correct
6 Correct 3 ms 4052 KB Output is correct
7 Correct 2 ms 3936 KB Output is correct
8 Correct 6 ms 4584 KB Output is correct
9 Correct 7 ms 4820 KB Output is correct
10 Correct 9 ms 5444 KB Output is correct
11 Correct 11 ms 5500 KB Output is correct
12 Correct 14 ms 5468 KB Output is correct
13 Correct 13 ms 5524 KB Output is correct
14 Correct 10 ms 5588 KB Output is correct
15 Correct 11 ms 5588 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3924 KB Output is correct
4 Correct 2 ms 3924 KB Output is correct
5 Correct 2 ms 4052 KB Output is correct
6 Correct 3 ms 4052 KB Output is correct
7 Correct 3 ms 4052 KB Output is correct
8 Correct 5 ms 4564 KB Output is correct
9 Correct 7 ms 4820 KB Output is correct
10 Correct 10 ms 5460 KB Output is correct
11 Correct 11 ms 5580 KB Output is correct
12 Correct 14 ms 5460 KB Output is correct
13 Correct 13 ms 5460 KB Output is correct
14 Correct 10 ms 5588 KB Output is correct
15 Correct 10 ms 5588 KB Output is correct
16 Correct 6 ms 5076 KB Output is correct
17 Correct 74 ms 6024 KB Output is correct
18 Correct 5 ms 5076 KB Output is correct
19 Correct 5 ms 5076 KB Output is correct
20 Correct 238 ms 6044 KB Output is correct
21 Correct 5 ms 5076 KB Output is correct
22 Correct 4 ms 5076 KB Output is correct
23 Correct 142 ms 6040 KB Output is correct
24 Correct 220 ms 6064 KB Output is correct
25 Correct 213 ms 6064 KB Output is correct
26 Correct 224 ms 6160 KB Output is correct
27 Correct 205 ms 6064 KB Output is correct
28 Correct 161 ms 6104 KB Output is correct
29 Correct 254 ms 6044 KB Output is correct
30 Correct 240 ms 5992 KB Output is correct
31 Correct 223 ms 6036 KB Output is correct
32 Correct 205 ms 6024 KB Output is correct
33 Correct 330 ms 6068 KB Output is correct
34 Correct 292 ms 6052 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3924 KB Output is correct
4 Correct 2 ms 3924 KB Output is correct
5 Correct 2 ms 4052 KB Output is correct
6 Correct 3 ms 4052 KB Output is correct
7 Correct 3 ms 4052 KB Output is correct
8 Correct 5 ms 4564 KB Output is correct
9 Correct 7 ms 4820 KB Output is correct
10 Correct 10 ms 5460 KB Output is correct
11 Correct 13 ms 5460 KB Output is correct
12 Correct 12 ms 5432 KB Output is correct
13 Correct 16 ms 5508 KB Output is correct
14 Correct 13 ms 5480 KB Output is correct
15 Correct 10 ms 5600 KB Output is correct
16 Correct 6 ms 5204 KB Output is correct
17 Correct 85 ms 6048 KB Output is correct
18 Correct 4 ms 5076 KB Output is correct
19 Correct 5 ms 5204 KB Output is correct
20 Correct 230 ms 6096 KB Output is correct
21 Correct 5 ms 5108 KB Output is correct
22 Correct 4 ms 5076 KB Output is correct
23 Correct 148 ms 5944 KB Output is correct
24 Correct 180 ms 6064 KB Output is correct
25 Correct 225 ms 6080 KB Output is correct
26 Correct 213 ms 6060 KB Output is correct
27 Correct 199 ms 5964 KB Output is correct
28 Correct 159 ms 6040 KB Output is correct
29 Correct 242 ms 6044 KB Output is correct
30 Correct 203 ms 5972 KB Output is correct
31 Correct 216 ms 6028 KB Output is correct
32 Correct 198 ms 6020 KB Output is correct
33 Correct 300 ms 6068 KB Output is correct
34 Correct 291 ms 6068 KB Output is correct
35 Correct 186 ms 6412 KB Output is correct
36 Correct 107 ms 6084 KB Output is correct
37 Correct 300 ms 6416 KB Output is correct
38 Correct 298 ms 6484 KB Output is correct
39 Correct 293 ms 6452 KB Output is correct
40 Correct 305 ms 6456 KB Output is correct
41 Correct 306 ms 6556 KB Output is correct
42 Execution timed out 1024 ms 6820 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3924 KB Output is correct
4 Correct 2 ms 3924 KB Output is correct
5 Correct 3 ms 3924 KB Output is correct
6 Correct 2 ms 4052 KB Output is correct
7 Correct 3 ms 4052 KB Output is correct
8 Correct 5 ms 4564 KB Output is correct
9 Correct 6 ms 4820 KB Output is correct
10 Correct 13 ms 5420 KB Output is correct
11 Correct 17 ms 5460 KB Output is correct
12 Correct 19 ms 5416 KB Output is correct
13 Correct 14 ms 5512 KB Output is correct
14 Correct 10 ms 5588 KB Output is correct
15 Correct 10 ms 5588 KB Output is correct
16 Correct 5 ms 5076 KB Output is correct
17 Correct 70 ms 5976 KB Output is correct
18 Correct 4 ms 5076 KB Output is correct
19 Correct 5 ms 5200 KB Output is correct
20 Correct 228 ms 6116 KB Output is correct
21 Correct 5 ms 5076 KB Output is correct
22 Correct 4 ms 5076 KB Output is correct
23 Correct 135 ms 6048 KB Output is correct
24 Correct 171 ms 6016 KB Output is correct
25 Correct 210 ms 6060 KB Output is correct
26 Correct 208 ms 6160 KB Output is correct
27 Correct 209 ms 6072 KB Output is correct
28 Correct 160 ms 6104 KB Output is correct
29 Correct 235 ms 6052 KB Output is correct
30 Correct 198 ms 6020 KB Output is correct
31 Correct 205 ms 6036 KB Output is correct
32 Correct 199 ms 6028 KB Output is correct
33 Correct 321 ms 6080 KB Output is correct
34 Correct 292 ms 6056 KB Output is correct
35 Correct 201 ms 6544 KB Output is correct
36 Correct 101 ms 6072 KB Output is correct
37 Correct 286 ms 6448 KB Output is correct
38 Correct 317 ms 6552 KB Output is correct
39 Correct 300 ms 6532 KB Output is correct
40 Correct 298 ms 6464 KB Output is correct
41 Correct 336 ms 6504 KB Output is correct
42 Correct 1000 ms 6968 KB Output is correct
43 Execution timed out 1033 ms 6748 KB Time limit exceeded
44 Halted 0 ms 0 KB -