| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 25563 |
2017-06-23T05:21:12 Z |
김동현(#1072) |
버스 (JOI14_bus) |
C++14 |
|
223 ms |
15776 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;
}
};
const int inf = 1e9;
struct Nod{
int v;
Nod *l, *r;
Nod() : v(inf), l(nullptr), r(nullptr) {}
};
const int sz = 86400001;
struct Seg{
Nod *rt;
void ini(){ rt = new Nod(); }
void upd(int x, int v, Nod *c, int p, int q){
if(p == q){ c->v = v; return; }
int m = (p + q) / 2;
if(x <= m){
if(c->l == nullptr) c->l = new Nod();
upd(x, v, c->l, p, m);
c->v = min(c->v, c->l->v);
}
else{
if(c->r == nullptr) c->r = new Nod();
upd(x, v, c->r, m + 1, q);
c->v = min(c->v, c->r->v);
}
}
void upd(int x, int v){ upd(x + 1, v, rt, 1, sz); }
int get(int s, int e, Nod *c, int p, int q){
if(e < p || q < s) return inf;
if(s <= p && q <= e) return c->v;
int m = (p + q) / 2, ret = inf;
if(c->l != nullptr) ret = min(ret, get(s, e, c->l, p, m));
if(c->r != nullptr) ret = min(ret, get(s, e, 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 = 2; i <= n; i++) S[i].ini();
for(auto &i : ql){
for(; j < m && el[j].et > i.t; j++){
Seg &cs = S[el[j].e], &ns = S[el[j].s];
int nst = cs.get(el[j].et, sz);
if(nst < inf){
if(el[j].s == 1) av.push_back({nst, el[j].st});
else ns.upd(el[j].st, nst);
}
}
S[n].upd(i.t, i.t);
}
sort(av.begin(), av.end());
for(auto &i : ql){
auto t = upper_bound(av.begin(), av.end(), (Ans){i.t, 0});
if(t == av.begin()) ans[i.i] = -1;
else ans[i.i] = (--t)->v;
}
for(int i = 0; i < q; i++) printf("%d\n", ans[i]);
}
Compilation message
bus.cpp: In function 'int main()':
bus.cpp:75: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:77: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:81:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
bus.cpp:83: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 |
Runtime error |
0 ms |
3212 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
3212 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
193 ms |
15584 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
223 ms |
15776 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
