oj.uz

Submission #25577

# Submission time Handle Problem Language Result Execution time Memory
25577 2017-06-23T05:57:11 Z khsoo01 버스 (JOI14_bus) C++11
100 / 100
 306 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 3 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 3 ms 6716 KB Output is correct
6 Correct 0 ms 6716 KB Output is correct
7 Correct 0 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 3 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 36 ms 6716 KB Output is correct
3 Correct 43 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 6 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 29 ms 6716 KB Output is correct
10 Correct 36 ms 6856 KB Output is correct
11 Correct 46 ms 6856 KB Output is correct
12 Correct 49 ms 6856 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 31376 KB Output is correct
2 Correct 239 ms 31376 KB Output is correct
3 Correct 246 ms 31376 KB Output is correct
4 Correct 209 ms 31376 KB Output is correct
5 Correct 273 ms 31376 KB Output is correct
6 Correct 249 ms 31376 KB Output is correct
7 Correct 256 ms 31376 KB Output is correct
8 Correct 253 ms 31376 KB Output is correct
9 Correct 226 ms 31376 KB Output is correct
10 Correct 249 ms 31376 KB Output is correct
11 Correct 239 ms 31376 KB Output is correct
12 Correct 199 ms 31376 KB Output is correct
13 Correct 213 ms 31376 KB Output is correct
14 Correct 203 ms 31376 KB Output is correct
15 Correct 219 ms 31376 KB Output is correct
16 Correct 99 ms 17096 KB Output is correct
17 Correct 93 ms 17096 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 31376 KB Output is correct
2 Correct 273 ms 31376 KB Output is correct
3 Correct 276 ms 31376 KB Output is correct
4 Correct 239 ms 31376 KB Output is correct
5 Correct 229 ms 31376 KB Output is correct
6 Correct 266 ms 31376 KB Output is correct
7 Correct 299 ms 31376 KB Output is correct
8 Correct 299 ms 31376 KB Output is correct
9 Correct 299 ms 31376 KB Output is correct
10 Correct 289 ms 31376 KB Output is correct
11 Correct 286 ms 31376 KB Output is correct
12 Correct 286 ms 31376 KB Output is correct
13 Correct 243 ms 31376 KB Output is correct
14 Correct 273 ms 31376 KB Output is correct
15 Correct 276 ms 31376 KB Output is correct
16 Correct 116 ms 17096 KB Output is correct