oj.uz

Submission #25571

# Submission time Handle Problem Language Result Execution time Memory
25571 2017-06-23T05:48:23 Z 김현수(#1073) 버스 (JOI14_bus) C++11
35 / 100
 403 ms 32156 KB 
#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;

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

void Insert (set<pll> &V, pll A) {
	auto it = V.lower_bound((pll){A.X, 0});
	if(it == V.end()) {V.insert(A); return;}
	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) {
		if(T.y == n) {
			Insert(can[T.x], {T.s, T.e});
			continue;
		}
		ll V = lb(can[T.y], T.e);
		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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6716 KB Output is correct
2 Correct 0 ms 6716 KB Output is correct
3 Correct 0 ms 6716 KB Output is correct
4 Correct 0 ms 6716 KB Output is correct
5 Correct 0 ms 6716 KB Output is correct
6 Correct 0 ms 6716 KB Output is correct
7 Correct 3 ms 6716 KB Output is correct
8 Correct 0 ms 6716 KB Output is correct
9 Correct 3 ms 6716 KB Output is correct
10 Correct 0 ms 6716 KB Output is correct
11 Correct 3 ms 6856 KB Output is correct
12 Correct 0 ms 6856 KB Output is correct
13 Correct 0 ms 6856 KB Output is correct
14 Correct 0 ms 6856 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 32024 KB Output is correct
2 Correct 299 ms 32024 KB Output is correct
3 Correct 299 ms 32024 KB Output is correct
4 Correct 276 ms 32024 KB Output is correct
5 Correct 323 ms 32024 KB Output is correct
6 Correct 279 ms 32024 KB Output is correct
7 Correct 266 ms 31376 KB Output is correct
8 Correct 356 ms 32156 KB Output is correct
9 Correct 359 ms 32024 KB Output is correct
10 Correct 233 ms 31376 KB Output is correct
11 Correct 236 ms 31376 KB Output is correct
12 Correct 253 ms 31376 KB Output is correct
13 Correct 253 ms 31376 KB Output is correct
14 Correct 226 ms 31376 KB Output is correct
15 Correct 263 ms 31376 KB Output is correct
16 Correct 99 ms 17096 KB Output is correct
17 Correct 106 ms 17096 KB Output is correct

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 32024 KB Output is correct
2 Correct 356 ms 32024 KB Output is correct
3 Correct 403 ms 32024 KB Output is correct
4 Correct 383 ms 32024 KB Output is correct
5 Correct 356 ms 32024 KB Output is correct
6 Correct 289 ms 32024 KB Output is correct
7 Correct 283 ms 31376 KB Output is correct
8 Correct 349 ms 32024 KB Output is correct
9 Correct 333 ms 32024 KB Output is correct
10 Incorrect 299 ms 31376 KB Output isn't correct
11 Halted 0 ms 0 KB -