oj.uz

Submission #42299

# Submission time Handle Problem Language Result Execution time Memory
42299 2018-02-25T16:36:27 Z minhtung0404 버스 (JOI14_bus) C++14
100 / 100
 606 ms 262144 KB 
#include<bits/stdc++.h>
const int N = 1e5 + 5;
const int M = 3e5 + 5;
const int inf = 1e9 + 7;
using namespace std;

vector <int> mv, adj[N], Min[N];
int n, m, q, num, a[M], b[M], x[M], y[M], dp[M];

bool cmp(int i, int j){
    if (y[i] > y[j]) return false;
    if (y[i] == y[j] && x[i] > x[j]) return false;
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> a[i] >> b[i] >> x[i] >> y[i];
        mv.push_back(i);
        adj[b[i]].push_back(i);
    }
    sort(mv.begin(), mv.end(), cmp);
    for (int i = 1; i <= n; i++) sort(adj[i].begin(), adj[i].end(), cmp);
    for (int ed = 0; ed < m; ed++){
        int i = mv[ed], u = a[i], v = b[i];
        if (u == 1) dp[ed] = x[i];
        else if (adj[u].size() == 0) dp[ed] = -inf;
        else{
            int l = 0, r = adj[u].size()-1;
            while (l != r){
                int mid = (l + r + 1) / 2;
                if (y[adj[u][mid]] <= x[i]) l = mid;
                else r = mid-1;
            }
            if (y[adj[u][l]] > x[i]) dp[ed] = -inf;
            else dp[ed] = Min[u][l];
        }
        if (Min[v].size() == 0) Min[v].push_back(dp[ed]);
        else Min[v].push_back(max(dp[ed], *Min[v].rbegin()));
    }
    cin >> q;
    while (q--){
        cin >> num;
        if (adj[n].size() == 0) cout << "-1\n";
        else{
            int l = 0, r = adj[n].size()-1;
            while (l != r){
                int mid = (l + r + 1)/ 2;
                if (y[adj[n][mid]] <= num) l = mid;
                else r = mid-1;
            }
            if (y[adj[n][l]] <= num && Min[n][l] != -inf) cout << Min[n][l] << "\n";
            else cout << "-1\n";
        }
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 6 ms 5228 KB Output is correct
3 Correct 6 ms 5228 KB Output is correct
4 Correct 6 ms 5268 KB Output is correct
5 Correct 7 ms 5288 KB Output is correct
6 Correct 7 ms 5476 KB Output is correct
7 Correct 6 ms 5592 KB Output is correct
8 Correct 6 ms 5592 KB Output is correct
9 Correct 8 ms 5592 KB Output is correct
10 Correct 6 ms 5592 KB Output is correct
11 Correct 7 ms 5748 KB Output is correct
12 Correct 7 ms 5892 KB Output is correct
13 Correct 7 ms 5892 KB Output is correct
14 Correct 7 ms 5892 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5892 KB Output is correct
2 Correct 187 ms 7688 KB Output is correct
3 Correct 176 ms 8360 KB Output is correct
4 Correct 23 ms 8360 KB Output is correct
5 Correct 23 ms 8360 KB Output is correct
6 Correct 22 ms 8360 KB Output is correct
7 Correct 161 ms 8360 KB Output is correct
8 Correct 6 ms 8360 KB Output is correct
9 Correct 159 ms 9012 KB Output is correct
10 Correct 181 ms 10236 KB Output is correct
11 Correct 158 ms 10512 KB Output is correct
12 Correct 197 ms 11792 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 33228 KB Output is correct
2 Correct 412 ms 41972 KB Output is correct
3 Correct 451 ms 50564 KB Output is correct
4 Correct 389 ms 59440 KB Output is correct
5 Correct 425 ms 67936 KB Output is correct
6 Correct 381 ms 76556 KB Output is correct
7 Correct 292 ms 82112 KB Output is correct
8 Correct 388 ms 93084 KB Output is correct
9 Correct 405 ms 101996 KB Output is correct
10 Correct 319 ms 106964 KB Output is correct
11 Correct 317 ms 114488 KB Output is correct
12 Correct 320 ms 121928 KB Output is correct
13 Correct 314 ms 129372 KB Output is correct
14 Correct 311 ms 136816 KB Output is correct
15 Correct 292 ms 144248 KB Output is correct
16 Correct 119 ms 144248 KB Output is correct
17 Correct 117 ms 146328 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 161668 KB Output is correct
2 Correct 556 ms 170916 KB Output is correct
3 Correct 569 ms 180840 KB Output is correct
4 Correct 604 ms 190424 KB Output is correct
5 Correct 555 ms 199568 KB Output is correct
6 Correct 606 ms 209112 KB Output is correct
7 Correct 479 ms 215780 KB Output is correct
8 Correct 561 ms 227868 KB Output is correct
9 Correct 552 ms 237492 KB Output is correct
10 Correct 513 ms 243480 KB Output is correct
11 Correct 460 ms 251864 KB Output is correct
12 Correct 452 ms 260096 KB Output is correct
13 Correct 470 ms 262144 KB Output is correct
14 Correct 476 ms 262144 KB Output is correct
15 Correct 459 ms 262144 KB Output is correct
16 Correct 286 ms 262144 KB Output is correct