| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 25572 |
2017-06-23T05:53:20 Z |
김동현(#1072) |
버스 (JOI14_bus) |
C++14 |
|
389 ms |
202696 KB |
#include <bits/stdc++.h>
using namespace std;
struct E{
int s, e, st, et;
bool operator<(const E &oth) const {
return et > oth.et;
}
};
struct Dat{
int st, ct;
bool operator<(const Dat &oth) const {
return ct == oth.ct ? st > oth.st : ct < oth.ct;
}
};
struct Qry{
int t, i;
bool operator<(const Qry &oth) const {
return t > oth.t;
}
};
struct Ans{
int t, v;
bool operator<(const Ans &oth) const {
return t == oth.t ? v > oth.v : t < oth.t;
}
};
struct Nod{ int v, l, r; };
Nod nv[16000010];
int cnt;
const int sz = 86400002, inf = 1e9;
struct Seg{
int rt;
int mak(){ nv[cnt] = {inf, -1, -1}; return cnt++; }
void ini(){ rt = mak(); }
void upd(int x, int v, int c, int p, int q){
if(p == q){ nv[c].v = min(nv[c].v, v); return; }
int m = (p + q) / 2;
if(x <= m){
if(nv[c].l < 0) nv[c].l = mak();
upd(x, v, nv[c].l, p, m);
nv[c].v = min(nv[c].v, nv[nv[c].l].v);
}
else{
if(nv[c].r < 0) nv[c].r = mak();
upd(x, v, nv[c].r, m + 1, q);
nv[c].v = min(nv[c].v, nv[nv[c].r].v);
}
}
void upd(int x, int v){ upd(x + 1, v, rt, 1, sz); }
int get(int s, int e, int c, int p, int q){
if(e < p || q < s) return inf;
if(s <= p && q <= e) return nv[c].v;
int m = (p + q) / 2, ret = inf;
if(nv[c].l >= 0) ret = min(ret, get(s, e, nv[c].l, p, m));
if(nv[c].r >= 0) ret = min(ret, get(s, e, nv[c].r, m + 1, q));
return ret;
}
int get(int s, int e){ return get(s + 1, e + 1, rt, 1, sz); }
} S[100010];
int n, m, q, j, ans[100010];
vector<Ans> av;
vector<E> el;
vector<Qry> ql;
int main(){
scanf("%d%d", &n, &m);
for(int i = 0, s, e, st, et; i < m; i++){
scanf("%d%d%d%d", &s, &e, &st, &et);
el.push_back({s, e, st, et});
}
sort(el.begin(), el.end());
scanf("%d", &q);
for(int i = 0, t; i < q; i++){
scanf("%d", &t);
ql.push_back({t, i});
}
ql.push_back({-1, q});
sort(ql.begin(), ql.end());
for(int i = 1; i <= n; i++) S[i].ini();
for(auto &i : ql){
for(; j < m && el[j].et > i.t; j++){
int nst = S[el[j].e].get(el[j].et, sz - 1);
if(nst < inf){
if(el[j].s == 1) S[1].upd(nst, -el[j].st);
else S[el[j].s].upd(el[j].st, nst);
}
}
S[n].upd(i.t, i.t);
}
sort(av.begin(), av.end());
for(auto &i : ql){
int t = -S[1].get(0, i.t);
ans[i.i] = max(-1, t);
}
for(int i = 0; i < q; i++) printf("%d\n", ans[i]);
}
Compilation message
bus.cpp: In function 'int main()':
bus.cpp:74:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
bus.cpp:76:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &s, &e, &st, &et);
^
bus.cpp:80:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
bus.cpp:82:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
190324 KB |
Output is correct |
| 2 |
Correct |
0 ms |
190324 KB |
Output is correct |
| 3 |
Correct |
0 ms |
190324 KB |
Output is correct |
| 4 |
Correct |
0 ms |
190324 KB |
Output is correct |
| 5 |
Correct |
0 ms |
190324 KB |
Output is correct |
| 6 |
Correct |
0 ms |
190324 KB |
Output is correct |
| 7 |
Correct |
0 ms |
190324 KB |
Output is correct |
| 8 |
Correct |
0 ms |
190324 KB |
Output is correct |
| 9 |
Correct |
0 ms |
190324 KB |
Output is correct |
| 10 |
Correct |
0 ms |
190324 KB |
Output is correct |
| 11 |
Correct |
0 ms |
190464 KB |
Output is correct |
| 12 |
Correct |
0 ms |
190464 KB |
Output is correct |
| 13 |
Correct |
0 ms |
190464 KB |
Output is correct |
| 14 |
Correct |
0 ms |
190464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
190324 KB |
Output is correct |
| 2 |
Incorrect |
83 ms |
191960 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
206 ms |
202696 KB |
Output is correct |
| 2 |
Correct |
223 ms |
202696 KB |
Output is correct |
| 3 |
Correct |
233 ms |
202696 KB |
Output is correct |
| 4 |
Correct |
236 ms |
202696 KB |
Output is correct |
| 5 |
Correct |
243 ms |
202696 KB |
Output is correct |
| 6 |
Correct |
229 ms |
202696 KB |
Output is correct |
| 7 |
Correct |
239 ms |
202696 KB |
Output is correct |
| 8 |
Correct |
199 ms |
202696 KB |
Output is correct |
| 9 |
Correct |
209 ms |
202696 KB |
Output is correct |
| 10 |
Correct |
269 ms |
202696 KB |
Output is correct |
| 11 |
Correct |
229 ms |
202696 KB |
Output is correct |
| 12 |
Correct |
389 ms |
202696 KB |
Output is correct |
| 13 |
Correct |
333 ms |
202696 KB |
Output is correct |
| 14 |
Correct |
343 ms |
202696 KB |
Output is correct |
| 15 |
Correct |
273 ms |
202696 KB |
Output is correct |
| 16 |
Correct |
103 ms |
193480 KB |
Output is correct |
| 17 |
Correct |
63 ms |
193480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
343 ms |
202696 KB |
Output is correct |
| 2 |
Correct |
316 ms |
202696 KB |
Output is correct |
| 3 |
Correct |
286 ms |
202696 KB |
Output is correct |
| 4 |
Correct |
343 ms |
202696 KB |
Output is correct |
| 5 |
Correct |
313 ms |
202696 KB |
Output is correct |
| 6 |
Correct |
359 ms |
202696 KB |
Output is correct |
| 7 |
Incorrect |
339 ms |
202696 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
