# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
25575 | 2017-06-23T05:55:27 Z | 서규호(#1074) | 버스 (JOI14_bus) | C++14 | 299 ms | 12224 KB |
#include <bits/stdc++.h> #define lld long long #define pp pair<int,int> #define pb push_back #define MOD 1000000007 #define left lleft #define right rright #define INF 2000000000 #define Linf 1000000000000000000LL #define next nnext #define minus mminus using namespace std; int N,M,Q,ans; struct data{ int x,y,tx,ty; }edge[300002]; vector<pair<int,pp>> d[100002]; priority_queue<pp> q; vector<int> print; int main(){ scanf("%d %d",&N,&M); for(int i=1; i<=M; i++){ scanf("%d %d %d %d",&edge[i].x,&edge[i].y,&edge[i].tx,&edge[i].ty); if(edge[i].x == 1) print.pb(edge[i].tx); } sort(edge+1,edge+M+1,[&](data &x,data &y){ return x.ty < y.ty; }); sort(print.begin(),print.end()); for(int i=0; i<print.size(); i++) d[1].pb({print[i],{i,i}}); for(int i=1; i<=M; i++){ int x,y,tx,ty; x = edge[i].x; y = edge[i].y; tx = edge[i].tx; ty = edge[i].ty; if(d[x].size() == 0 || d[x][0].first > tx) continue; int l,r,t; l = 0; r = d[x].size()-1; while(l <= r){ int mid = (l+r)/2; if(d[x][mid].first <= tx){ t = mid; l = mid+1; }else r = mid-1; } int e = d[x][t].second.second; if(d[y].size() == 0 || d[y].back().second.second < e){ int tt; if(d[y].size() == 0) tt = 0; else tt = d[y].back().second.second+1; d[y].pb({ty,{tt,e}}); } } scanf("%d",&Q); for(int i=1; i<=Q; i++){ int query; scanf("%d",&query); if(d[N].size() == 0 || query < d[N][0].first){ ans = -1; }else{ int l,r,t; l = 0; r = d[N].size()-1; while(l <= r){ int mid = (l+r)/2; if(d[N][mid].first <= query){ t = mid; l = mid+1; }else r = mid-1; } t = d[N][t].second.second; ans = print[t]; } printf("%d\n",ans); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 9056 KB | Output is correct |
2 | Correct | 0 ms | 9056 KB | Output is correct |
3 | Correct | 0 ms | 9056 KB | Output is correct |
4 | Correct | 0 ms | 9056 KB | Output is correct |
5 | Correct | 0 ms | 9056 KB | Output is correct |
6 | Correct | 0 ms | 9056 KB | Output is correct |
7 | Correct | 0 ms | 9056 KB | Output is correct |
8 | Correct | 0 ms | 9056 KB | Output is correct |
9 | Correct | 0 ms | 9056 KB | Output is correct |
10 | Correct | 3 ms | 9056 KB | Output is correct |
11 | Correct | 3 ms | 9056 KB | Output is correct |
12 | Correct | 3 ms | 9056 KB | Output is correct |
13 | Correct | 0 ms | 9188 KB | Output is correct |
14 | Correct | 0 ms | 9192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 9056 KB | Output is correct |
2 | Correct | 23 ms | 9056 KB | Output is correct |
3 | Correct | 36 ms | 9056 KB | Output is correct |
4 | Correct | 3 ms | 9056 KB | Output is correct |
5 | Correct | 3 ms | 9056 KB | Output is correct |
6 | Correct | 3 ms | 9056 KB | Output is correct |
7 | Correct | 36 ms | 9056 KB | Output is correct |
8 | Correct | 0 ms | 9056 KB | Output is correct |
9 | Correct | 33 ms | 9056 KB | Output is correct |
10 | Correct | 33 ms | 9056 KB | Output is correct |
11 | Correct | 23 ms | 9188 KB | Output is correct |
12 | Correct | 36 ms | 9192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 229 ms | 9056 KB | Output is correct |
2 | Correct | 199 ms | 9056 KB | Output is correct |
3 | Correct | 279 ms | 9056 KB | Output is correct |
4 | Correct | 206 ms | 9056 KB | Output is correct |
5 | Correct | 243 ms | 9056 KB | Output is correct |
6 | Correct | 189 ms | 9332 KB | Output is correct |
7 | Correct | 213 ms | 9596 KB | Output is correct |
8 | Correct | 253 ms | 10708 KB | Output is correct |
9 | Correct | 243 ms | 9332 KB | Output is correct |
10 | Correct | 193 ms | 9320 KB | Output is correct |
11 | Correct | 203 ms | 9320 KB | Output is correct |
12 | Correct | 229 ms | 9320 KB | Output is correct |
13 | Correct | 243 ms | 9320 KB | Output is correct |
14 | Correct | 236 ms | 9320 KB | Output is correct |
15 | Correct | 196 ms | 9320 KB | Output is correct |
16 | Correct | 73 ms | 12224 KB | Output is correct |
17 | Correct | 69 ms | 12224 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 269 ms | 9056 KB | Output is correct |
2 | Correct | 263 ms | 9056 KB | Output is correct |
3 | Correct | 263 ms | 9056 KB | Output is correct |
4 | Correct | 233 ms | 9056 KB | Output is correct |
5 | Correct | 233 ms | 9056 KB | Output is correct |
6 | Correct | 246 ms | 9332 KB | Output is correct |
7 | Correct | 253 ms | 9596 KB | Output is correct |
8 | Correct | 299 ms | 9332 KB | Output is correct |
9 | Correct | 283 ms | 9332 KB | Output is correct |
10 | Correct | 243 ms | 9320 KB | Output is correct |
11 | Correct | 203 ms | 9320 KB | Output is correct |
12 | Correct | 266 ms | 9320 KB | Output is correct |
13 | Correct | 223 ms | 9320 KB | Output is correct |
14 | Correct | 263 ms | 9320 KB | Output is correct |
15 | Correct | 276 ms | 9320 KB | Output is correct |
16 | Correct | 89 ms | 12224 KB | Output is correct |