# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
8370 |
2014-09-13T15:09:17 Z |
gs14004 |
버스 (JOI14_bus) |
C++ |
|
264 ms |
14712 KB |
#include <cstdio>
#include <queue>
#include <algorithm>
#include <utility>
#include <cstring>
using namespace std;
typedef pair<int,int> pi;
int res[100005];
pi query[100005];
struct ln{int pos,s,e;};
priority_queue<ln> graph[100005];
bool operator<(ln a, ln b){return a.e > b.e;}
struct cmp{bool operator()(ln a, ln b){return a.s < b.s;}};
int n,m,q;
int before = -1;
int v[100005];
void process(int lim, int save){
priority_queue<ln,vector<ln>,cmp> pq;
// e small guy out
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()) {
// s big guy out
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 |
4 ms |
5896 KB |
Output is correct |
13 |
Correct |
4 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 |
28 ms |
5896 KB |
Output is correct |
3 |
Correct |
52 ms |
5896 KB |
Output is correct |
4 |
Correct |
8 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 |
32 ms |
5896 KB |
Output is correct |
8 |
Correct |
0 ms |
5896 KB |
Output is correct |
9 |
Correct |
32 ms |
5896 KB |
Output is correct |
10 |
Correct |
36 ms |
5896 KB |
Output is correct |
11 |
Correct |
40 ms |
5896 KB |
Output is correct |
12 |
Correct |
32 ms |
5896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
200 ms |
11836 KB |
Output is correct |
2 |
Correct |
216 ms |
11836 KB |
Output is correct |
3 |
Correct |
208 ms |
11836 KB |
Output is correct |
4 |
Correct |
204 ms |
11836 KB |
Output is correct |
5 |
Correct |
204 ms |
11836 KB |
Output is correct |
6 |
Correct |
208 ms |
11852 KB |
Output is correct |
7 |
Correct |
188 ms |
11724 KB |
Output is correct |
8 |
Correct |
196 ms |
11732 KB |
Output is correct |
9 |
Correct |
212 ms |
11964 KB |
Output is correct |
10 |
Correct |
168 ms |
13568 KB |
Output is correct |
11 |
Correct |
168 ms |
12380 KB |
Output is correct |
12 |
Correct |
172 ms |
14712 KB |
Output is correct |
13 |
Correct |
180 ms |
14712 KB |
Output is correct |
14 |
Correct |
160 ms |
13572 KB |
Output is correct |
15 |
Correct |
164 ms |
12980 KB |
Output is correct |
16 |
Correct |
80 ms |
8932 KB |
Output is correct |
17 |
Correct |
60 ms |
8932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
248 ms |
11836 KB |
Output is correct |
2 |
Correct |
264 ms |
11836 KB |
Output is correct |
3 |
Correct |
256 ms |
11836 KB |
Output is correct |
4 |
Correct |
240 ms |
11836 KB |
Output is correct |
5 |
Correct |
244 ms |
11836 KB |
Output is correct |
6 |
Correct |
240 ms |
11852 KB |
Output is correct |
7 |
Correct |
232 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 |
224 ms |
12376 KB |
Output is correct |
11 |
Correct |
236 ms |
12380 KB |
Output is correct |
12 |
Correct |
236 ms |
12372 KB |
Output is correct |
13 |
Correct |
212 ms |
12376 KB |
Output is correct |
14 |
Correct |
224 ms |
12380 KB |
Output is correct |
15 |
Correct |
220 ms |
12376 KB |
Output is correct |
16 |
Correct |
108 ms |
8932 KB |
Output is correct |