| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 8371 |
2014-09-13T15:11:13 Z |
gs14004 |
버스 (JOI14_bus) |
C++ |
|
256 ms |
14712 KB |
#include <cstdio>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int,int> pi;
int res[100005];
pi query[100005];
struct ln{int pos,s,e;};
bool operator<(ln a, ln b){return a.e > b.e;}
struct cmp{bool operator()(ln a, ln b){return a.s < b.s;}};
struct cmp2{bool operator()(ln a, ln b){return a.e > b.e;}};
priority_queue<ln,vector<ln>,cmp2> graph[100005];
int n,m,q,v[100005];
void process(int lim, int save){
priority_queue<ln,vector<ln>,cmp> pq;
int pos = n;
while (!graph[pos].empty()) {
ln t = graph[pos].top();
if(t.e > lim) break;
graph[pos].pop();
if(v[t.pos] > t.s) continue;
pq.push(t);
}
while (!pq.empty()) {
ln t = pq.top();
pos = t.pos;
v[pos] = t.s;
pq.pop();
if(pos == 1) break;
while (!graph[pos].empty()) {
ln u = graph[pos].top();
if(u.e > t.s) break;
graph[pos].pop();
if(v[u.pos] > u.s) continue;
pq.push(u);
}
}
res[save] = v[1];
}
int main(){
v[1] = -1;
int p,q,r,s;
scanf("%d %d",&n,&m);
for (int i=0; i<m; i++) {
scanf("%d %d %d %d",&p,&q,&r,&s);
graph[q].push({ p,r,s});
}
scanf("%d",&q);
for (int i=0; i<q; i++) {
scanf("%d",&query[i].first);
query[i].second = i;
}
sort(query,query+q);
for (int i=0; i<q; i++) {
process(query[i].first,query[i].second);
}
for (int i=0; i<q; i++) {
printf("%d\n",res[i]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 2 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 3 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 4 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 5 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 6 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 7 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 8 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 9 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 10 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 11 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 12 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 13 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 14 |
Correct |
0 ms |
5896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 2 |
Correct |
44 ms |
5896 KB |
Output is correct |
| 3 |
Correct |
24 ms |
5896 KB |
Output is correct |
| 4 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 5 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5896 KB |
Output is correct |
| 7 |
Correct |
36 ms |
5896 KB |
Output is correct |
| 8 |
Correct |
0 ms |
5896 KB |
Output is correct |
| 9 |
Correct |
44 ms |
5896 KB |
Output is correct |
| 10 |
Correct |
36 ms |
5896 KB |
Output is correct |
| 11 |
Correct |
36 ms |
5896 KB |
Output is correct |
| 12 |
Correct |
40 ms |
5896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
11836 KB |
Output is correct |
| 2 |
Correct |
212 ms |
11836 KB |
Output is correct |
| 3 |
Correct |
212 ms |
11836 KB |
Output is correct |
| 4 |
Correct |
204 ms |
11836 KB |
Output is correct |
| 5 |
Correct |
200 ms |
11836 KB |
Output is correct |
| 6 |
Correct |
216 ms |
11852 KB |
Output is correct |
| 7 |
Correct |
192 ms |
11724 KB |
Output is correct |
| 8 |
Correct |
200 ms |
11732 KB |
Output is correct |
| 9 |
Correct |
208 ms |
11964 KB |
Output is correct |
| 10 |
Correct |
164 ms |
13568 KB |
Output is correct |
| 11 |
Correct |
168 ms |
12380 KB |
Output is correct |
| 12 |
Correct |
164 ms |
14712 KB |
Output is correct |
| 13 |
Correct |
176 ms |
14712 KB |
Output is correct |
| 14 |
Correct |
176 ms |
13572 KB |
Output is correct |
| 15 |
Correct |
164 ms |
12980 KB |
Output is correct |
| 16 |
Correct |
64 ms |
8932 KB |
Output is correct |
| 17 |
Correct |
52 ms |
8932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
252 ms |
11836 KB |
Output is correct |
| 2 |
Correct |
240 ms |
11836 KB |
Output is correct |
| 3 |
Correct |
248 ms |
11836 KB |
Output is correct |
| 4 |
Correct |
256 ms |
11836 KB |
Output is correct |
| 5 |
Correct |
240 ms |
11836 KB |
Output is correct |
| 6 |
Correct |
248 ms |
11852 KB |
Output is correct |
| 7 |
Correct |
244 ms |
11724 KB |
Output is correct |
| 8 |
Correct |
248 ms |
11840 KB |
Output is correct |
| 9 |
Correct |
248 ms |
11836 KB |
Output is correct |
| 10 |
Correct |
228 ms |
12376 KB |
Output is correct |
| 11 |
Correct |
224 ms |
12380 KB |
Output is correct |
| 12 |
Correct |
220 ms |
12372 KB |
Output is correct |
| 13 |
Correct |
224 ms |
12376 KB |
Output is correct |
| 14 |
Correct |
216 ms |
12380 KB |
Output is correct |
| 15 |
Correct |
216 ms |
12376 KB |
Output is correct |
| 16 |
Correct |
108 ms |
8932 KB |
Output is correct |
