Submission #25562

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
25562	2017-06-23T05:12:39 Z	김현수(#1073)	버스 (JOI14_bus)	C++11	0 / 100	413 ms	29128 KB

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;
bool chk[N];

vector<pll> can[N], ans;

struct sexy {
	ll s, e, x, y;
	bool operator < (const sexy &T) const {
		return (y > T.y);
	}
};

vector<sexy> a;

bool comp (pll A, pll B) {
	if(A.X != B.X) return A.X > B.X;
	return A.Y < B.Y;
}

void arrange (vector<pll> &V) {
	vector<pll> X;
	for(auto &T : V) X.push_back(T);
	V.clear();
	sort(X.begin(), X.end(), comp);
	ll mn = inf;
	for(auto &T : X) {
		if(mn > T.Y) V.push_back(T);
		mn = min(mn, T.Y);
	}
	reverse(V.begin(), V.end());
}

ll lb (vector<pll> &V, ll X) {
	auto it = lower_bound(V.begin(), V.end(), (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) {
		if(T.y == n) {
			can[T.x].push_back({T.s, T.e});
			continue;
		}
		if(!chk[T.y]) {
			arrange(can[T.y]);
			chk[T.y] = true;
		}
		ll V = lb(can[T.y], T.e);
		can[T.x].push_back({T.s, V});
	}
	arrange(can[1]);
	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

bus.cpp: In function 'int main()':
bus.cpp:55: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:58: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:78:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&q);
                  ^
bus.cpp:81:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&T);
                   ^

Subtask #1

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	4468 KB	Output is correct
2	Correct	0 ms	4468 KB	Output is correct
3	Correct	0 ms	4468 KB	Output is correct
4	Correct	0 ms	4468 KB	Output is correct
5	Correct	0 ms	4468 KB	Output is correct
6	Correct	0 ms	4468 KB	Output is correct
7	Correct	0 ms	4468 KB	Output is correct
8	Correct	0 ms	4468 KB	Output is correct
9	Incorrect	0 ms	4468 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #2

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	4468 KB	Output is correct
2	Correct	33 ms	4468 KB	Output is correct
3	Correct	33 ms	4468 KB	Output is correct
4	Correct	0 ms	4468 KB	Output is correct
5	Correct	0 ms	4468 KB	Output is correct
6	Incorrect	3 ms	4468 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	319 ms	29128 KB	Output is correct
2	Correct	273 ms	29128 KB	Output is correct
3	Correct	253 ms	29128 KB	Output is correct
4	Correct	329 ms	29128 KB	Output is correct
5	Correct	319 ms	29128 KB	Output is correct
6	Correct	313 ms	29128 KB	Output is correct
7	Correct	276 ms	29128 KB	Output is correct
8	Correct	336 ms	29128 KB	Output is correct
9	Correct	349 ms	29128 KB	Output is correct
10	Correct	243 ms	29128 KB	Output is correct
11	Incorrect	259 ms	29128 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	339 ms	29128 KB	Output is correct
2	Correct	413 ms	29128 KB	Output is correct
3	Correct	326 ms	29128 KB	Output is correct
4	Correct	313 ms	29128 KB	Output is correct
5	Correct	333 ms	29128 KB	Output is correct
6	Correct	353 ms	29128 KB	Output is correct
7	Incorrect	299 ms	29128 KB	Output isn't correct
8	Halted	0 ms	0 KB	-