oj.uz

Submission #707347

# Submission time Handle Problem Language Result Execution time Memory
707347 2023-03-08T20:04:13 Z Stickfish Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 124856 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;
        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][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;
                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 4 ms 6996 KB Output is correct
2 Correct 3 ms 6996 KB Output is correct
3 Correct 4 ms 7124 KB Output is correct
4 Correct 4 ms 7124 KB Output is correct
5 Correct 4 ms 7124 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 4 ms 7124 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6996 KB Output is correct
2 Correct 4 ms 6996 KB Output is correct
3 Correct 4 ms 7124 KB Output is correct
4 Correct 4 ms 7096 KB Output is correct
5 Correct 4 ms 7128 KB Output is correct
6 Correct 4 ms 7124 KB Output is correct
7 Correct 4 ms 7124 KB Output is correct
8 Correct 7 ms 7892 KB Output is correct
9 Correct 9 ms 8404 KB Output is correct
10 Correct 13 ms 9300 KB Output is correct
11 Correct 15 ms 9336 KB Output is correct
12 Correct 14 ms 9320 KB Output is correct
13 Correct 15 ms 9328 KB Output is correct
14 Correct 14 ms 9388 KB Output is correct
15 Correct 15 ms 9364 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6984 KB Output is correct
2 Correct 3 ms 6996 KB Output is correct
3 Correct 3 ms 7124 KB Output is correct
4 Correct 3 ms 7124 KB Output is correct
5 Correct 4 ms 7212 KB Output is correct
6 Correct 6 ms 7124 KB Output is correct
7 Correct 4 ms 7124 KB Output is correct
8 Correct 8 ms 7892 KB Output is correct
9 Correct 11 ms 8460 KB Output is correct
10 Correct 14 ms 9300 KB Output is correct
11 Correct 15 ms 9344 KB Output is correct
12 Correct 14 ms 9328 KB Output is correct
13 Correct 15 ms 9332 KB Output is correct
14 Correct 14 ms 9288 KB Output is correct
15 Correct 14 ms 9384 KB Output is correct
16 Correct 10 ms 10708 KB Output is correct
17 Correct 113 ms 15700 KB Output is correct
18 Correct 44 ms 25144 KB Output is correct
19 Correct 42 ms 27420 KB Output is correct
20 Correct 392 ms 27592 KB Output is correct
21 Correct 11 ms 12500 KB Output is correct
22 Correct 35 ms 25428 KB Output is correct
23 Correct 306 ms 23800 KB Output is correct
24 Correct 372 ms 26580 KB Output is correct
25 Correct 445 ms 27568 KB Output is correct
26 Correct 382 ms 27432 KB Output is correct
27 Correct 371 ms 27536 KB Output is correct
28 Correct 398 ms 27604 KB Output is correct
29 Correct 356 ms 27536 KB Output is correct
30 Correct 364 ms 27416 KB Output is correct
31 Correct 358 ms 27532 KB Output is correct
32 Correct 385 ms 27520 KB Output is correct
33 Correct 354 ms 27600 KB Output is correct
34 Correct 352 ms 27604 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6996 KB Output is correct
2 Correct 3 ms 6996 KB Output is correct
3 Correct 5 ms 7132 KB Output is correct
4 Correct 4 ms 7124 KB Output is correct
5 Correct 4 ms 7124 KB Output is correct
6 Correct 5 ms 7208 KB Output is correct
7 Correct 4 ms 7156 KB Output is correct
8 Correct 6 ms 7892 KB Output is correct
9 Correct 9 ms 8404 KB Output is correct
10 Correct 13 ms 9312 KB Output is correct
11 Correct 15 ms 9300 KB Output is correct
12 Correct 13 ms 9324 KB Output is correct
13 Correct 15 ms 9332 KB Output is correct
14 Correct 13 ms 9300 KB Output is correct
15 Correct 13 ms 9300 KB Output is correct
16 Correct 8 ms 10708 KB Output is correct
17 Correct 124 ms 15780 KB Output is correct
18 Correct 33 ms 25164 KB Output is correct
19 Correct 41 ms 27468 KB Output is correct
20 Correct 392 ms 27680 KB Output is correct
21 Correct 11 ms 12500 KB Output is correct
22 Correct 34 ms 25476 KB Output is correct
23 Correct 288 ms 23800 KB Output is correct
24 Correct 399 ms 26664 KB Output is correct
25 Correct 390 ms 27568 KB Output is correct
26 Correct 373 ms 27540 KB Output is correct
27 Correct 356 ms 27536 KB Output is correct
28 Correct 408 ms 27712 KB Output is correct
29 Correct 351 ms 27468 KB Output is correct
30 Correct 382 ms 27516 KB Output is correct
31 Correct 348 ms 27644 KB Output is correct
32 Correct 360 ms 27432 KB Output is correct
33 Correct 363 ms 27604 KB Output is correct
34 Correct 345 ms 27536 KB Output is correct
35 Correct 269 ms 22544 KB Output is correct
36 Correct 181 ms 19084 KB Output is correct
37 Correct 389 ms 27228 KB Output is correct
38 Correct 396 ms 27924 KB Output is correct
39 Correct 398 ms 28108 KB Output is correct
40 Correct 400 ms 27980 KB Output is correct
41 Correct 395 ms 28008 KB Output is correct
42 Correct 377 ms 27876 KB Output is correct
43 Correct 387 ms 27764 KB Output is correct
44 Correct 858 ms 27932 KB Output is correct
45 Correct 305 ms 28416 KB Output is correct
46 Correct 308 ms 28400 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6996 KB Output is correct
2 Correct 3 ms 6868 KB Output is correct
3 Correct 3 ms 7124 KB Output is correct
4 Correct 3 ms 7124 KB Output is correct
5 Correct 4 ms 7124 KB Output is correct
6 Correct 4 ms 7124 KB Output is correct
7 Correct 4 ms 7124 KB Output is correct
8 Correct 7 ms 7892 KB Output is correct
9 Correct 11 ms 8404 KB Output is correct
10 Correct 13 ms 9300 KB Output is correct
11 Correct 16 ms 9344 KB Output is correct
12 Correct 14 ms 9300 KB Output is correct
13 Correct 15 ms 9304 KB Output is correct
14 Correct 13 ms 9392 KB Output is correct
15 Correct 14 ms 9388 KB Output is correct
16 Correct 10 ms 10716 KB Output is correct
17 Correct 111 ms 15688 KB Output is correct
18 Correct 34 ms 25172 KB Output is correct
19 Correct 38 ms 27532 KB Output is correct
20 Correct 390 ms 27672 KB Output is correct
21 Correct 11 ms 12500 KB Output is correct
22 Correct 34 ms 25468 KB Output is correct
23 Correct 294 ms 23800 KB Output is correct
24 Correct 385 ms 26696 KB Output is correct
25 Correct 398 ms 27568 KB Output is correct
26 Correct 364 ms 27560 KB Output is correct
27 Correct 363 ms 27540 KB Output is correct
28 Correct 385 ms 27592 KB Output is correct
29 Correct 353 ms 27536 KB Output is correct
30 Correct 353 ms 27424 KB Output is correct
31 Correct 352 ms 27524 KB Output is correct
32 Correct 356 ms 27428 KB Output is correct
33 Correct 337 ms 27596 KB Output is correct
34 Correct 337 ms 27592 KB Output is correct
35 Correct 272 ms 22604 KB Output is correct
36 Correct 185 ms 19084 KB Output is correct
37 Correct 386 ms 27212 KB Output is correct
38 Correct 392 ms 27988 KB Output is correct
39 Correct 398 ms 27948 KB Output is correct
40 Correct 391 ms 27948 KB Output is correct
41 Correct 398 ms 27928 KB Output is correct
42 Correct 383 ms 27804 KB Output is correct
43 Correct 390 ms 27888 KB Output is correct
44 Correct 858 ms 27980 KB Output is correct
45 Correct 301 ms 28412 KB Output is correct
46 Correct 301 ms 28428 KB Output is correct
47 Execution timed out 1085 ms 124856 KB Time limit exceeded
48 Halted 0 ms 0 KB -