oj.uz

Submission #751646

# Submission time Handle Problem Language Result Execution time Memory
751646 2023-06-01T05:30:37 Z JooDdae 버스 (JOI14_bus) C++17
100 / 100
 286 ms 22884 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int INF = 1e9;

int n, m, q, in[300300];
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
vector<array<int, 2>> v[100100];

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        pq.push({c, i, a}), pq.push({d, -i, b});
    }

    memset(in, -1, sizeof in);

    while(!pq.empty()) {
        auto [t, id, u] = pq.top(); pq.pop();

        if(id < 0) {
            id = -id;
            if(in[id] < 0 || (!v[u].empty() && v[u].back()[1] >= in[id])) continue;
            v[u].push_back({t, in[id]});
        } else {
            if(u == 1) in[id] = t;
            else if(!v[u].empty()) in[id] = v[u].back()[1];
        }
    }

    cin >> q;
    while(q--) {
        int x; cin >> x;

        auto it = lower_bound(v[n].begin(), v[n].end(), array<int, 2>({x, INF}));
        cout << (it == v[n].begin() ? -1 : (*prev(it))[1]) << "\n";
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3796 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 3 ms 3836 KB Output is correct
5 Correct 3 ms 3796 KB Output is correct
6 Correct 3 ms 3796 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 2 ms 3836 KB Output is correct
9 Correct 3 ms 3796 KB Output is correct
10 Correct 2 ms 3796 KB Output is correct
11 Correct 3 ms 3924 KB Output is correct
12 Correct 3 ms 3924 KB Output is correct
13 Correct 3 ms 3924 KB Output is correct
14 Correct 3 ms 3924 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3832 KB Output is correct
2 Correct 24 ms 5452 KB Output is correct
3 Correct 23 ms 5452 KB Output is correct
4 Correct 4 ms 3924 KB Output is correct
5 Correct 4 ms 3924 KB Output is correct
6 Correct 5 ms 3924 KB Output is correct
7 Correct 16 ms 4440 KB Output is correct
8 Correct 3 ms 3796 KB Output is correct
9 Correct 18 ms 4512 KB Output is correct
10 Correct 24 ms 5464 KB Output is correct
11 Correct 17 ms 4700 KB Output is correct
12 Correct 26 ms 5616 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 16372 KB Output is correct
2 Correct 239 ms 16560 KB Output is correct
3 Correct 233 ms 16300 KB Output is correct
4 Correct 237 ms 16308 KB Output is correct
5 Correct 246 ms 16460 KB Output is correct
6 Correct 253 ms 16452 KB Output is correct
7 Correct 253 ms 16300 KB Output is correct
8 Correct 253 ms 16344 KB Output is correct
9 Correct 236 ms 16328 KB Output is correct
10 Correct 243 ms 16300 KB Output is correct
11 Correct 234 ms 21756 KB Output is correct
12 Correct 229 ms 21772 KB Output is correct
13 Correct 258 ms 21712 KB Output is correct
14 Correct 230 ms 21676 KB Output is correct
15 Correct 226 ms 21716 KB Output is correct
16 Correct 77 ms 11740 KB Output is correct
17 Correct 81 ms 11700 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 16388 KB Output is correct
2 Correct 262 ms 16328 KB Output is correct
3 Correct 246 ms 16396 KB Output is correct
4 Correct 250 ms 16364 KB Output is correct
5 Correct 252 ms 16328 KB Output is correct
6 Correct 272 ms 16192 KB Output is correct
7 Correct 268 ms 16336 KB Output is correct
8 Correct 269 ms 22872 KB Output is correct
9 Correct 278 ms 22884 KB Output is correct
10 Correct 258 ms 21648 KB Output is correct
11 Correct 286 ms 21760 KB Output is correct
12 Correct 244 ms 21704 KB Output is correct
13 Correct 246 ms 21672 KB Output is correct
14 Correct 247 ms 21764 KB Output is correct
15 Correct 248 ms 21700 KB Output is correct
16 Correct 96 ms 12640 KB Output is correct