제출 #25577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
25577		khsoo01	버스 (JOI14_bus)	C++11	100 / 100	306 ms	31376 KiB

bus

#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));
	}
}

컴파일 시 표준 에러 (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);
                   ^

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50