oj.uz

Submission #1117375

# Submission time Handle Problem Language Result Execution time Memory
1117375 2024-11-23T13:11:44 Z _callmelucian Escape Route 2 (JOI24_escape2) C++14
100 / 100
 592 ms 129392 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5, Q = 3e5 + 5;
//const int limFlight = 10, limQuery = 10;
const int limFlight = 316, limQuery = 1000;

vector<pl> flight[mn], nxt[18][mn], qry[mn];
vector<ll> save[mn];
ll best[mn], ans[Q], n, T;

void refine (vector<pl> &vec) {
    priority_queue<pl> pq;
    sort(all(vec), [&] (pl a, pl b)
         { return (a.first == b.first ? a.second > b.second : a.first < b.first); });

    for (pl item : vec) {
        ll a, b; tie(a, b) = item;
        while (pq.size() && pq.top().first >= b) pq.pop();
        pq.emplace(b, a);
    }
    vec.clear();

    while (pq.size()) {
        ll a, b; tie(b, a) = pq.top(); pq.pop();
        vec.emplace_back(a, b);
    }
    reverse(all(vec));
}

ll quickJump (int u, int flightID, int step) {
    ll ans = 0;
    for (int i = 0; step; step >>= 1, i++) {
        if ((step & 1) == 0) continue;
        ll weight; tie(flightID, weight) = nxt[i][u][flightID];
        u += (1 << i), ans += weight;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    /// read flights info
    cin >> n >> T;
    for (int i = 1; i < n; i++) {
        int m; cin >> m;
        flight[i].resize(m);
        for (pl &it : flight[i])
            cin >> it.first >> it.second;
        refine(flight[i]);
        assert(flight[i].size());
    }

    for (int s = 0; s < 18; s++)
        for (int i = 1; i < n; i++) nxt[s][i].resize(flight[i].size());

    /// construct edges + bin-lift pre-compute
    for (int i = 1; i + 1 < n; i++) {
        int iter = 0;
        for (int j = 0; j < flight[i].size(); j++) {
            while (iter < flight[i + 1].size() && flight[i][j].second > flight[i + 1][iter].first) iter++;
            if (iter < flight[i + 1].size())
                nxt[0][i][j] = {iter, flight[i + 1][iter].second - flight[i][j].second};
            else nxt[0][i][j] = {0, flight[i + 1][0].second + T - flight[i][j].second};

//            cout << "(" << i << ", " << j << ") -> (" << i + 1 << ", " << nxt[0][i][j].first << "), weight " << nxt[0][i][j].second << "\n";
        }
    }
    for (int s = 1; s < 18; s++) {
        for (int i = 1; i + (1 << s) < n; i++) {
            for (int j = 0; j < flight[i].size(); j++) {
                ll id, weight; tie(id, weight) = nxt[s - 1][i][j];
                ll nxtID, nxtWeight; tie(nxtID, nxtWeight) = nxt[s - 1][i + (1 << (s - 1))][id];
                nxt[s][i][j] = {nxtID, weight + nxtWeight};
            }
        }
    }

    /// read queries
    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        qry[l].emplace_back(r, i);
    }

    /// process queries
    for (int i = 1; i < n; i++) {
        if (qry[i].empty()) continue;
        if (flight[i].size() > limFlight || qry[i].size() > limQuery) { // calculate for every possible R
            for (int j = i; j < n; j++) save[j] = vector<ll>(flight[j].size(), LLONG_MAX);
            for (int k = 0; k < flight[i].size(); k++)
                save[i][k] = flight[i][k].second - flight[i][k].first;
            for (int j = i; j + 1 < n; j++) {
                for (int k = 0; k < flight[j].size(); k++) {
                    if (save[j][k] == LLONG_MAX) continue;
                    ll nxtID, weight; tie(nxtID, weight) = nxt[0][j][k];
                    save[j + 1][nxtID] = min(save[j + 1][nxtID], save[j][k] + weight);
                }
            }
            for (int j = i; j < n; j++) best[j] = *min_element(all(save[j]));
            for (pii item : qry[i]) {
                int r, idx; tie(r, idx) = item;
                ans[idx] = best[r - 1];
            }
        }
        else { // simply brute-force
            for (pii item : qry[i]) {
                int r, idx; tie(r, idx) = item;
                ans[idx] = LLONG_MAX;
                for (int k = 0; k < flight[i].size(); k++)
                    ans[idx] = min(ans[idx], quickJump(i, k, r - i - 1) + flight[i][k].second - flight[i][k].first);
            }
        }
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:72:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int j = 0; j < flight[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~
Main.cpp:73:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             while (iter < flight[i + 1].size() && flight[i][j].second > flight[i + 1][iter].first) iter++;
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             if (iter < flight[i + 1].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:83:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for (int j = 0; j < flight[i].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~~~
Main.cpp:103:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             for (int k = 0; k < flight[i].size(); k++)
      |                             ~~^~~~~~~~~~~~~~~~~~
Main.cpp:106:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |                 for (int k = 0; k < flight[j].size(); k++) {
      |                                 ~~^~~~~~~~~~~~~~~~~~
Main.cpp:122:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |                 for (int k = 0; k < flight[i].size(); k++)
      |                                 ~~^~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49760 KB Output is correct
2 Correct 86 ms 61112 KB Output is correct
3 Correct 92 ms 63144 KB Output is correct
4 Correct 102 ms 67400 KB Output is correct
5 Correct 91 ms 63816 KB Output is correct
6 Correct 106 ms 67660 KB Output is correct
7 Correct 105 ms 67752 KB Output is correct
8 Correct 89 ms 63784 KB Output is correct
9 Correct 104 ms 67700 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49760 KB Output is correct
2 Correct 86 ms 61112 KB Output is correct
3 Correct 92 ms 63144 KB Output is correct
4 Correct 102 ms 67400 KB Output is correct
5 Correct 91 ms 63816 KB Output is correct
6 Correct 106 ms 67660 KB Output is correct
7 Correct 105 ms 67752 KB Output is correct
8 Correct 89 ms 63784 KB Output is correct
9 Correct 104 ms 67700 KB Output is correct
10 Correct 40 ms 49736 KB Output is correct
11 Correct 97 ms 65608 KB Output is correct
12 Correct 99 ms 65356 KB Output is correct
13 Correct 100 ms 65096 KB Output is correct
14 Correct 99 ms 65360 KB Output is correct
15 Correct 108 ms 65900 KB Output is correct
16 Correct 85 ms 60940 KB Output is correct
17 Correct 110 ms 66632 KB Output is correct
18 Correct 117 ms 65860 KB Output is correct
19 Correct 106 ms 66888 KB Output is correct
20 Correct 104 ms 66128 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49760 KB Output is correct
2 Correct 86 ms 61112 KB Output is correct
3 Correct 92 ms 63144 KB Output is correct
4 Correct 102 ms 67400 KB Output is correct
5 Correct 91 ms 63816 KB Output is correct
6 Correct 106 ms 67660 KB Output is correct
7 Correct 105 ms 67752 KB Output is correct
8 Correct 89 ms 63784 KB Output is correct
9 Correct 104 ms 67700 KB Output is correct
10 Correct 227 ms 110236 KB Output is correct
11 Correct 293 ms 129096 KB Output is correct
12 Correct 304 ms 129096 KB Output is correct
13 Correct 281 ms 124744 KB Output is correct
14 Correct 311 ms 129192 KB Output is correct
15 Correct 315 ms 129348 KB Output is correct
16 Correct 239 ms 110724 KB Output is correct
17 Correct 321 ms 129392 KB Output is correct
18 Correct 182 ms 110408 KB Output is correct
19 Correct 185 ms 109640 KB Output is correct
20 Correct 181 ms 110460 KB Output is correct
21 Correct 180 ms 110664 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49760 KB Output is correct
2 Correct 86 ms 61112 KB Output is correct
3 Correct 92 ms 63144 KB Output is correct
4 Correct 102 ms 67400 KB Output is correct
5 Correct 91 ms 63816 KB Output is correct
6 Correct 106 ms 67660 KB Output is correct
7 Correct 105 ms 67752 KB Output is correct
8 Correct 89 ms 63784 KB Output is correct
9 Correct 104 ms 67700 KB Output is correct
10 Correct 40 ms 49736 KB Output is correct
11 Correct 97 ms 65608 KB Output is correct
12 Correct 99 ms 65356 KB Output is correct
13 Correct 100 ms 65096 KB Output is correct
14 Correct 99 ms 65360 KB Output is correct
15 Correct 108 ms 65900 KB Output is correct
16 Correct 85 ms 60940 KB Output is correct
17 Correct 110 ms 66632 KB Output is correct
18 Correct 117 ms 65860 KB Output is correct
19 Correct 106 ms 66888 KB Output is correct
20 Correct 104 ms 66128 KB Output is correct
21 Correct 227 ms 110236 KB Output is correct
22 Correct 293 ms 129096 KB Output is correct
23 Correct 304 ms 129096 KB Output is correct
24 Correct 281 ms 124744 KB Output is correct
25 Correct 311 ms 129192 KB Output is correct
26 Correct 315 ms 129348 KB Output is correct
27 Correct 239 ms 110724 KB Output is correct
28 Correct 321 ms 129392 KB Output is correct
29 Correct 182 ms 110408 KB Output is correct
30 Correct 185 ms 109640 KB Output is correct
31 Correct 181 ms 110460 KB Output is correct
32 Correct 180 ms 110664 KB Output is correct
33 Correct 244 ms 104792 KB Output is correct
34 Correct 224 ms 104744 KB Output is correct
35 Correct 222 ms 101448 KB Output is correct
36 Correct 245 ms 101488 KB Output is correct
37 Correct 267 ms 105032 KB Output is correct
38 Correct 235 ms 103752 KB Output is correct
39 Correct 275 ms 118088 KB Output is correct
40 Correct 218 ms 95048 KB Output is correct
41 Correct 237 ms 100868 KB Output is correct
42 Correct 280 ms 115996 KB Output is correct
43 Correct 231 ms 97252 KB Output is correct
44 Correct 244 ms 100852 KB Output is correct
45 Correct 189 ms 101536 KB Output is correct
46 Correct 159 ms 92556 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 49744 KB Output is correct
2 Correct 36 ms 49764 KB Output is correct
3 Correct 319 ms 82760 KB Output is correct
4 Correct 309 ms 82816 KB Output is correct
5 Correct 304 ms 82596 KB Output is correct
6 Correct 314 ms 82708 KB Output is correct
7 Correct 349 ms 82760 KB Output is correct
8 Correct 218 ms 70216 KB Output is correct
9 Correct 105 ms 83528 KB Output is correct
10 Correct 93 ms 69148 KB Output is correct
11 Correct 196 ms 110528 KB Output is correct
12 Correct 180 ms 101448 KB Output is correct
13 Correct 144 ms 92488 KB Output is correct
14 Correct 123 ms 89664 KB Output is correct
15 Correct 128 ms 90168 KB Output is correct
16 Correct 116 ms 88916 KB Output is correct
17 Correct 128 ms 89928 KB Output is correct
18 Correct 131 ms 83948 KB Output is correct
19 Correct 218 ms 83272 KB Output is correct
20 Correct 230 ms 105592 KB Output is correct
21 Correct 375 ms 102728 KB Output is correct
22 Correct 488 ms 93036 KB Output is correct
23 Correct 395 ms 92768 KB Output is correct
24 Correct 147 ms 94496 KB Output is correct
25 Correct 134 ms 94228 KB Output is correct
26 Correct 145 ms 94764 KB Output is correct
27 Correct 209 ms 109612 KB Output is correct
28 Correct 228 ms 110408 KB Output is correct
29 Correct 200 ms 110664 KB Output is correct
30 Correct 95 ms 63036 KB Output is correct
31 Correct 70 ms 57368 KB Output is correct
32 Correct 102 ms 64584 KB Output is correct
33 Correct 79 ms 57928 KB Output is correct
34 Correct 96 ms 60488 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49760 KB Output is correct
2 Correct 86 ms 61112 KB Output is correct
3 Correct 92 ms 63144 KB Output is correct
4 Correct 102 ms 67400 KB Output is correct
5 Correct 91 ms 63816 KB Output is correct
6 Correct 106 ms 67660 KB Output is correct
7 Correct 105 ms 67752 KB Output is correct
8 Correct 89 ms 63784 KB Output is correct
9 Correct 104 ms 67700 KB Output is correct
10 Correct 40 ms 49736 KB Output is correct
11 Correct 97 ms 65608 KB Output is correct
12 Correct 99 ms 65356 KB Output is correct
13 Correct 100 ms 65096 KB Output is correct
14 Correct 99 ms 65360 KB Output is correct
15 Correct 108 ms 65900 KB Output is correct
16 Correct 85 ms 60940 KB Output is correct
17 Correct 110 ms 66632 KB Output is correct
18 Correct 117 ms 65860 KB Output is correct
19 Correct 106 ms 66888 KB Output is correct
20 Correct 104 ms 66128 KB Output is correct
21 Correct 227 ms 110236 KB Output is correct
22 Correct 293 ms 129096 KB Output is correct
23 Correct 304 ms 129096 KB Output is correct
24 Correct 281 ms 124744 KB Output is correct
25 Correct 311 ms 129192 KB Output is correct
26 Correct 315 ms 129348 KB Output is correct
27 Correct 239 ms 110724 KB Output is correct
28 Correct 321 ms 129392 KB Output is correct
29 Correct 182 ms 110408 KB Output is correct
30 Correct 185 ms 109640 KB Output is correct
31 Correct 181 ms 110460 KB Output is correct
32 Correct 180 ms 110664 KB Output is correct
33 Correct 244 ms 104792 KB Output is correct
34 Correct 224 ms 104744 KB Output is correct
35 Correct 222 ms 101448 KB Output is correct
36 Correct 245 ms 101488 KB Output is correct
37 Correct 267 ms 105032 KB Output is correct
38 Correct 235 ms 103752 KB Output is correct
39 Correct 275 ms 118088 KB Output is correct
40 Correct 218 ms 95048 KB Output is correct
41 Correct 237 ms 100868 KB Output is correct
42 Correct 280 ms 115996 KB Output is correct
43 Correct 231 ms 97252 KB Output is correct
44 Correct 244 ms 100852 KB Output is correct
45 Correct 189 ms 101536 KB Output is correct
46 Correct 159 ms 92556 KB Output is correct
47 Correct 37 ms 49744 KB Output is correct
48 Correct 36 ms 49764 KB Output is correct
49 Correct 319 ms 82760 KB Output is correct
50 Correct 309 ms 82816 KB Output is correct
51 Correct 304 ms 82596 KB Output is correct
52 Correct 314 ms 82708 KB Output is correct
53 Correct 349 ms 82760 KB Output is correct
54 Correct 218 ms 70216 KB Output is correct
55 Correct 105 ms 83528 KB Output is correct
56 Correct 93 ms 69148 KB Output is correct
57 Correct 196 ms 110528 KB Output is correct
58 Correct 180 ms 101448 KB Output is correct
59 Correct 144 ms 92488 KB Output is correct
60 Correct 123 ms 89664 KB Output is correct
61 Correct 128 ms 90168 KB Output is correct
62 Correct 116 ms 88916 KB Output is correct
63 Correct 128 ms 89928 KB Output is correct
64 Correct 131 ms 83948 KB Output is correct
65 Correct 218 ms 83272 KB Output is correct
66 Correct 230 ms 105592 KB Output is correct
67 Correct 375 ms 102728 KB Output is correct
68 Correct 488 ms 93036 KB Output is correct
69 Correct 395 ms 92768 KB Output is correct
70 Correct 147 ms 94496 KB Output is correct
71 Correct 134 ms 94228 KB Output is correct
72 Correct 145 ms 94764 KB Output is correct
73 Correct 209 ms 109612 KB Output is correct
74 Correct 228 ms 110408 KB Output is correct
75 Correct 200 ms 110664 KB Output is correct
76 Correct 95 ms 63036 KB Output is correct
77 Correct 70 ms 57368 KB Output is correct
78 Correct 102 ms 64584 KB Output is correct
79 Correct 79 ms 57928 KB Output is correct
80 Correct 96 ms 60488 KB Output is correct
81 Correct 554 ms 96268 KB Output is correct
82 Correct 559 ms 96092 KB Output is correct
83 Correct 592 ms 95868 KB Output is correct
84 Correct 565 ms 96072 KB Output is correct
85 Correct 549 ms 96072 KB Output is correct
86 Correct 323 ms 82248 KB Output is correct
87 Correct 173 ms 96972 KB Output is correct
88 Correct 525 ms 96584 KB Output is correct
89 Correct 538 ms 96996 KB Output is correct
90 Correct 333 ms 82764 KB Output is correct
91 Correct 110 ms 77140 KB Output is correct
92 Correct 185 ms 104764 KB Output is correct
93 Correct 213 ms 105416 KB Output is correct
94 Correct 201 ms 104276 KB Output is correct
95 Correct 222 ms 105152 KB Output is correct
96 Correct 232 ms 97308 KB Output is correct
97 Correct 337 ms 96584 KB Output is correct
98 Correct 346 ms 118800 KB Output is correct
99 Correct 371 ms 119224 KB Output is correct
100 Correct 298 ms 109188 KB Output is correct
101 Correct 333 ms 108896 KB Output is correct
102 Correct 214 ms 108696 KB Output is correct
103 Correct 190 ms 107656 KB Output is correct
104 Correct 211 ms 108564 KB Output is correct
105 Correct 141 ms 71752 KB Output is correct
106 Correct 107 ms 66176 KB Output is correct
107 Correct 189 ms 76876 KB Output is correct
108 Correct 144 ms 68740 KB Output is correct
109 Correct 158 ms 71496 KB Output is correct