Submission #25577

#TimeUsernameProblemLanguageResultExecution timeMemory
25577khsoo01버스 (JOI14_bus)C++11
100 / 100
306 ms31376 KiB
#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)

bus.cpp: In function 'int main()':
bus.cpp:53:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&m);
                         ^
bus.cpp:56:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld",&X,&Y,&S,&E);
                                        ^
bus.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&q);
                  ^
bus.cpp:70:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&T);
                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...