oj.uz

Submission #25576

# Submission time Handle Problem Language Result Execution time Memory
25576 2017-06-23T05:55:55 Z 김현수(#1073) 버스 (JOI14_bus) C++11
100 / 100
 296 ms 31376 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;

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

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.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 3 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 3 ms 6716 KB Output is correct
11 Correct 6 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6716 KB Output is correct
2 Correct 29 ms 6716 KB Output is correct
3 Correct 36 ms 6716 KB Output is correct
4 Correct 3 ms 6716 KB Output is correct
5 Correct 6 ms 6716 KB Output is correct
6 Correct 3 ms 6716 KB Output is correct
7 Correct 26 ms 6716 KB Output is correct
8 Correct 0 ms 6716 KB Output is correct
9 Correct 33 ms 6716 KB Output is correct
10 Correct 36 ms 6856 KB Output is correct
11 Correct 23 ms 6856 KB Output is correct
12 Correct 43 ms 6856 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 31376 KB Output is correct
2 Correct 253 ms 31376 KB Output is correct
3 Correct 213 ms 31376 KB Output is correct
4 Correct 203 ms 31376 KB Output is correct
5 Correct 219 ms 31376 KB Output is correct
6 Correct 219 ms 31376 KB Output is correct
7 Correct 216 ms 31376 KB Output is correct
8 Correct 256 ms 31376 KB Output is correct
9 Correct 223 ms 31376 KB Output is correct
10 Correct 179 ms 31376 KB Output is correct
11 Correct 209 ms 31376 KB Output is correct
12 Correct 233 ms 31376 KB Output is correct
13 Correct 223 ms 31376 KB Output is correct
14 Correct 203 ms 31376 KB Output is correct
15 Correct 246 ms 31376 KB Output is correct
16 Correct 79 ms 17096 KB Output is correct
17 Correct 79 ms 17096 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 31376 KB Output is correct
2 Correct 283 ms 31376 KB Output is correct
3 Correct 266 ms 31376 KB Output is correct
4 Correct 269 ms 31376 KB Output is correct
5 Correct 296 ms 31376 KB Output is correct
6 Correct 279 ms 31376 KB Output is correct
7 Correct 259 ms 31376 KB Output is correct
8 Correct 259 ms 31376 KB Output is correct
9 Correct 249 ms 31376 KB Output is correct
10 Correct 286 ms 31376 KB Output is correct
11 Correct 266 ms 31376 KB Output is correct
12 Correct 249 ms 31376 KB Output is correct
13 Correct 289 ms 31376 KB Output is correct
14 Correct 246 ms 31376 KB Output is correct
15 Correct 253 ms 31376 KB Output is correct
16 Correct 123 ms 17096 KB Output is correct