# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
25577 | khsoo01 | 버스 (JOI14_bus) | C++11 | 306 ms | 31376 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 100005, M = 300005, inf = 1e18;
ll n, m, q;
set<pll> can[N];
vector<pll> ans;
struct sexy {
ll s, e, x, y;
bool operator < (const sexy &T) const {
return (e > T.e);
}
};
vector<sexy> a;
void Insert (set<pll> &V, pll A) {
auto it = V.lower_bound((pll){A.X, 0});
if(it != V.end()) {
if(it->Y <= A.Y) return;
if(it->X == A.X) V.erase(it);
}
V.insert(A);
while(true) {
it = V.find(A);
if(it == V.begin()) break;
it--;
if(A.Y <= it->Y) V.erase(it);
else break;
}
}
ll lb (set<pll> &V, ll X) {
auto it = V.lower_bound((pll){X, 0});
if(it == V.end()) return inf;
return it->second;
}
ll ub (vector<pll> &V, ll X) {
auto it = upper_bound(V.begin(), V.end(), (pll){X, inf});
if(it == V.begin()) return inf; it--;
return it->second;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=m;i++) {
ll S, E, X, Y;
scanf("%lld%lld%lld%lld",&X,&Y,&S,&E);
a.push_back({S, E, X, Y});
}
sort(a.begin(), a.end());
for(auto &T : a) {
ll V = (T.y == n ? T.e : lb(can[T.y], T.e));
if(V != inf) Insert(can[T.x], {T.s, V});
}
for(auto &T : can[1]) {
ans.push_back({T.Y, T.X});
}
scanf("%lld",&q);
while(q--) {
ll T, V;
scanf("%lld",&T);
V = ub(ans, T);
printf("%lld\n",(V == inf ? -1 : V));
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |