oj.uz

Submission #620197

# Submission time Handle Problem Language Result Execution time Memory
620197 2022-08-03T03:20:18 Z joelau Road Construction (JOI21_road_construction) C++14
7 / 100
 5274 ms 27540 KB 
#include <bits/stdc++.h>
using namespace std;

long long N,K, ft[250005];
pair<long long,long long> A[250005];
vector< tuple<long long,long long,long long> > lst;
vector<long long> dis,ans;
set< pair<long long,long long> > s;

void update (long long x, long long v) {
	x++;
	while (x <= N) ft[x] += v, x += x & -x;
}

long long query (long long x) {
	x++;
	long long ans = 0;
	while (x) ans += ft[x], x -= x & -x;
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> K;
	for (long long i = 0; i < N; ++i) {
		long long x,y; cin >> x >> y;
		A[i] = make_pair(x-y,x+y);
		dis.push_back(x+y);
	}
	sort(dis.begin(),dis.end());
	dis.resize(unique(dis.begin(),dis.end()) - dis.begin());
	long long low = 0, high = 4e9+5;
	while (high-low > 1) {
		long long mid = (low+high)/2;
		lst.clear();
		for (long long i = 0; i < N; ++i) {
			long long n = lower_bound(dis.begin(),dis.end(),A[i].second) - dis.begin();
			lst.emplace_back(A[i].first,0,n);
			lst.emplace_back(A[i].first+mid,1,n);
		}
		sort(lst.begin(),lst.end());
		for (long long i = 0; i <= N; ++i) ft[i] = 0;
		long long cnt = 0;
		for (auto x: lst) {
			long long a,b,c; tie(a,b,c) = x;
			if (b == 0) {
				long long n = lower_bound(dis.begin(),dis.end(),dis[c]-mid) - dis.begin();
				long long m = upper_bound(dis.begin(),dis.end(),dis[c]+mid) - dis.begin() - 1;
				cnt += query(m) - query(n-1);
				update(c,1);
			}
			else update(c,-1);
		}
		if (cnt >= K) high = mid;
		else low = mid;
	}
	lst.clear();
	for (long long i = 0; i < N; ++i) {
		long long n = lower_bound(dis.begin(),dis.end(),A[i].second) - dis.begin();
		lst.emplace_back(A[i].first,0,n);
		lst.emplace_back(A[i].first+low,1,n);
	}
	sort(lst.begin(),lst.end());
	for (auto x: lst) {
		long long a,b,c; tie(a,b,c) = x;
		if (b == 0) {
			long long n = lower_bound(dis.begin(),dis.end(),dis[c]-low) - dis.begin();
			auto it = s.lower_bound(make_pair(n,-1));
			while (it != s.end() && abs(dis[it->first]-dis[c]) <= low) {
				ans.push_back(max(abs(dis[it->first]-dis[c]),abs(it->second-a)));
				it++;
			}
			s.emplace(c,a);
		}
		else s.erase(make_pair(c,a-low));
	}
	sort(ans.begin(),ans.end());
	for (long long x: ans) cout << x << '\n';
	for (long long i = ans.size(); i < K; ++i) cout << high << '\n';
	
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 5060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3642 ms 27540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5256 ms 26432 KB Output is correct
2 Correct 5274 ms 26480 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 3724 ms 24224 KB Output is correct
5 Correct 3213 ms 26728 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5256 ms 26432 KB Output is correct
2 Correct 5274 ms 26480 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 3724 ms 24224 KB Output is correct
5 Correct 3213 ms 26728 KB Output is correct
6 Incorrect 5179 ms 26576 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 5060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 5060 KB Output isn't correct
2 Halted 0 ms 0 KB -