#include <bits/stdc++.h>
using namespace std;
struct E{
int s, e, st, et;
bool operator<(const E &oth) const {
return st < oth.st;
}
};
struct Qry{
int t, i;
bool operator<(const Qry &oth) const {
return t > oth.t;
}
};
struct Nod{ int v, l, r; };
Nod nv[19000010];
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 = max(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 = max(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 = max(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 = max(ret, get(s, e, nv[c].l, p, m));
if(nv[c].r >= 0) ret = max(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, t[100010];
vector<E> el;
vector<Qry> ql;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) S[i].ini();
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});
S[1].upd(st, st);
}
sort(el.begin(), el.end());
scanf("%d", &q);
for(int i = 0; i < q; i++){
scanf("%d", t + i);
}
for(auto &i : el){
int nst = S[i.s].get(0, i.st);
if(nst >= 0) S[i.e].upd(i.et, nst);
}
for(int i = 0; i < q; i++){
int v = S[n].get(0, t[i]);
printf("%d\n", v < 0 ? -1 : v);
}
}
Compilation message
bus.cpp: In function 'int main()':
bus.cpp:59: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:62: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:67:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
bus.cpp:69:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", t + i);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
225472 KB |
Output is correct |
| 2 |
Correct |
0 ms |
225472 KB |
Output is correct |
| 3 |
Correct |
0 ms |
225472 KB |
Output is correct |
| 4 |
Correct |
0 ms |
225472 KB |
Output is correct |
| 5 |
Correct |
0 ms |
225472 KB |
Output is correct |
| 6 |
Correct |
0 ms |
225472 KB |
Output is correct |
| 7 |
Correct |
0 ms |
225472 KB |
Output is correct |
| 8 |
Correct |
0 ms |
225472 KB |
Output is correct |
| 9 |
Correct |
0 ms |
225472 KB |
Output is correct |
| 10 |
Correct |
0 ms |
225472 KB |
Output is correct |
| 11 |
Correct |
3 ms |
225612 KB |
Output is correct |
| 12 |
Correct |
3 ms |
225612 KB |
Output is correct |
| 13 |
Correct |
3 ms |
225612 KB |
Output is correct |
| 14 |
Correct |
0 ms |
225612 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
225472 KB |
Output is correct |
| 2 |
Correct |
49 ms |
225472 KB |
Output is correct |
| 3 |
Correct |
36 ms |
225472 KB |
Output is correct |
| 4 |
Correct |
6 ms |
225472 KB |
Output is correct |
| 5 |
Correct |
0 ms |
225472 KB |
Output is correct |
| 6 |
Correct |
3 ms |
225472 KB |
Output is correct |
| 7 |
Correct |
36 ms |
225472 KB |
Output is correct |
| 8 |
Correct |
0 ms |
225472 KB |
Output is correct |
| 9 |
Correct |
33 ms |
225472 KB |
Output is correct |
| 10 |
Correct |
46 ms |
225612 KB |
Output is correct |
| 11 |
Correct |
33 ms |
225612 KB |
Output is correct |
| 12 |
Correct |
63 ms |
225612 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
619 ms |
237844 KB |
Output is correct |
| 2 |
Correct |
426 ms |
237844 KB |
Output is correct |
| 3 |
Correct |
563 ms |
237844 KB |
Output is correct |
| 4 |
Correct |
463 ms |
237844 KB |
Output is correct |
| 5 |
Correct |
443 ms |
237844 KB |
Output is correct |
| 6 |
Correct |
426 ms |
237844 KB |
Output is correct |
| 7 |
Correct |
596 ms |
237844 KB |
Output is correct |
| 8 |
Correct |
606 ms |
237844 KB |
Output is correct |
| 9 |
Correct |
533 ms |
237844 KB |
Output is correct |
| 10 |
Correct |
689 ms |
237844 KB |
Output is correct |
| 11 |
Correct |
686 ms |
237844 KB |
Output is correct |
| 12 |
Correct |
669 ms |
237844 KB |
Output is correct |
| 13 |
Correct |
606 ms |
237844 KB |
Output is correct |
| 14 |
Correct |
619 ms |
237844 KB |
Output is correct |
| 15 |
Correct |
543 ms |
237844 KB |
Output is correct |
| 16 |
Correct |
213 ms |
228628 KB |
Output is correct |
| 17 |
Correct |
173 ms |
228628 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
519 ms |
237844 KB |
Output is correct |
| 2 |
Correct |
556 ms |
237844 KB |
Output is correct |
| 3 |
Correct |
503 ms |
237844 KB |
Output is correct |
| 4 |
Correct |
496 ms |
237844 KB |
Output is correct |
| 5 |
Correct |
439 ms |
237844 KB |
Output is correct |
| 6 |
Correct |
496 ms |
237844 KB |
Output is correct |
| 7 |
Correct |
606 ms |
237844 KB |
Output is correct |
| 8 |
Correct |
583 ms |
237844 KB |
Output is correct |
| 9 |
Correct |
619 ms |
237844 KB |
Output is correct |
| 10 |
Correct |
776 ms |
237844 KB |
Output is correct |
| 11 |
Correct |
609 ms |
237844 KB |
Output is correct |
| 12 |
Correct |
636 ms |
237844 KB |
Output is correct |
| 13 |
Correct |
749 ms |
237844 KB |
Output is correct |
| 14 |
Correct |
733 ms |
237844 KB |
Output is correct |
| 15 |
Correct |
673 ms |
237844 KB |
Output is correct |
| 16 |
Correct |
229 ms |
228628 KB |
Output is correct |
