| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 6801 |
2014-07-07T14:42:15 Z |
Qwaz |
버스 (JOI14_bus) |
C++ |
|
232 ms |
17136 KB |
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair < int, int > pii;
const int MAX = 300020, INF = 123456789;
struct bus {
int s, t, sTime, eTime;
bus() {}
bus(int s, int t, int sTime, int eTime) : s(s), t(t), sTime(sTime), eTime(eTime) {}
bool operator < (const bus &t) const {
return eTime < t.eTime;
}
};
int n, m, numQuery, query[MAX];
bus data[MAX];
void input(){
scanf("%d%d", &n, &m);
int i;
for(i = 0; i<m; i++){
int a, b, x, y;
scanf("%d%d%d%d", &a, &b, &x, &y);
data[i] = bus(a, b, x, y);
}
sort(data, data+m);
scanf("%d", &numQuery);
for(i = 0; i<numQuery; i++)
scanf("%d", &query[i]);
}
//(도달시간, 출발시간)
vector < pii > time[MAX];
int getLast(int target, int t){
pii find = pii(t+1, 0);
vector < pii > &v = time[target];
if(v.size() == 0) return -INF;
int index = lower_bound(v.begin(), v.end(), find)-v.begin();
if(index == 0) return -INF;
return v[index-1].second;
}
void solve(){
time[1].push_back(pii(0, 0));
int i;
for(i = 0; i<m; i++){
bus &now = data[i];
int last;
if(now.s == 1) last = now.sTime;
else last = getLast(now.s, now.sTime);
if(last != -INF && (time[now.t].size() == 0 || time[now.t][time[now.t].size()-1].second < last))
time[now.t].push_back(pii(now.eTime, last));
}
for(i = 0; i<numQuery; i++){
int res = getLast(n, query[i]);
printf("%d\n", res == -INF ? -1 : res);
}
}
int main(){
input();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
14100 KB |
Output is correct |
| 3 |
Correct |
0 ms |
14100 KB |
Output is correct |
| 4 |
Correct |
0 ms |
14100 KB |
Output is correct |
| 5 |
Correct |
4 ms |
14100 KB |
Output is correct |
| 6 |
Correct |
0 ms |
14100 KB |
Output is correct |
| 7 |
Correct |
4 ms |
14100 KB |
Output is correct |
| 8 |
Correct |
0 ms |
14100 KB |
Output is correct |
| 9 |
Correct |
0 ms |
14100 KB |
Output is correct |
| 10 |
Correct |
4 ms |
14100 KB |
Output is correct |
| 11 |
Correct |
4 ms |
14100 KB |
Output is correct |
| 12 |
Correct |
0 ms |
14100 KB |
Output is correct |
| 13 |
Correct |
4 ms |
14100 KB |
Output is correct |
| 14 |
Correct |
0 ms |
14100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
14100 KB |
Output is correct |
| 2 |
Correct |
32 ms |
14100 KB |
Output is correct |
| 3 |
Correct |
36 ms |
14100 KB |
Output is correct |
| 4 |
Correct |
0 ms |
14100 KB |
Output is correct |
| 5 |
Correct |
4 ms |
14100 KB |
Output is correct |
| 6 |
Correct |
0 ms |
14100 KB |
Output is correct |
| 7 |
Correct |
28 ms |
14100 KB |
Output is correct |
| 8 |
Correct |
0 ms |
14100 KB |
Output is correct |
| 9 |
Correct |
28 ms |
14100 KB |
Output is correct |
| 10 |
Correct |
36 ms |
14100 KB |
Output is correct |
| 11 |
Correct |
24 ms |
14100 KB |
Output is correct |
| 12 |
Correct |
40 ms |
14100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
14100 KB |
Output is correct |
| 2 |
Correct |
168 ms |
14100 KB |
Output is correct |
| 3 |
Correct |
180 ms |
14100 KB |
Output is correct |
| 4 |
Correct |
192 ms |
14100 KB |
Output is correct |
| 5 |
Correct |
180 ms |
14100 KB |
Output is correct |
| 6 |
Correct |
172 ms |
14232 KB |
Output is correct |
| 7 |
Correct |
188 ms |
14496 KB |
Output is correct |
| 8 |
Correct |
200 ms |
15156 KB |
Output is correct |
| 9 |
Correct |
192 ms |
14232 KB |
Output is correct |
| 10 |
Correct |
188 ms |
14232 KB |
Output is correct |
| 11 |
Correct |
176 ms |
14232 KB |
Output is correct |
| 12 |
Correct |
196 ms |
14232 KB |
Output is correct |
| 13 |
Correct |
184 ms |
14232 KB |
Output is correct |
| 14 |
Correct |
180 ms |
14100 KB |
Output is correct |
| 15 |
Correct |
180 ms |
14232 KB |
Output is correct |
| 16 |
Correct |
68 ms |
17136 KB |
Output is correct |
| 17 |
Correct |
68 ms |
17136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
208 ms |
14100 KB |
Output is correct |
| 2 |
Correct |
200 ms |
14100 KB |
Output is correct |
| 3 |
Correct |
224 ms |
14100 KB |
Output is correct |
| 4 |
Correct |
220 ms |
14100 KB |
Output is correct |
| 5 |
Correct |
216 ms |
14100 KB |
Output is correct |
| 6 |
Correct |
220 ms |
14232 KB |
Output is correct |
| 7 |
Correct |
224 ms |
14496 KB |
Output is correct |
| 8 |
Correct |
204 ms |
14232 KB |
Output is correct |
| 9 |
Correct |
232 ms |
14232 KB |
Output is correct |
| 10 |
Correct |
212 ms |
14232 KB |
Output is correct |
| 11 |
Correct |
216 ms |
14232 KB |
Output is correct |
| 12 |
Correct |
208 ms |
14232 KB |
Output is correct |
| 13 |
Correct |
204 ms |
14232 KB |
Output is correct |
| 14 |
Correct |
216 ms |
14100 KB |
Output is correct |
| 15 |
Correct |
192 ms |
14232 KB |
Output is correct |
| 16 |
Correct |
92 ms |
17136 KB |
Output is correct |
