oj.uz

Submission #618958

# Submission time Handle Problem Language Result Execution time Memory
618958 2022-08-02T08:37:14 Z joelau Road Construction (JOI21_road_construction) C++14
7 / 100
 10000 ms 39172 KB 
#include <bits/stdc++.h>
using namespace std;

long long N,K,ft[250005];
pair<long long,long long> lst[250005];
vector< tuple<long long,long long,long long,long long> > A;
vector<long long> dis;
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;
		lst[i] = make_pair(x-y,x+y);
		dis.push_back(lst[i].second);
	}
	sort(dis.begin(),dis.end());
	dis.resize(unique(dis.begin(),dis.end()) - dis.begin());
	s.emplace(0,0); s.emplace(N*N,4e9+5);
	for (long long i = 1; i <= K; ++i) {
		auto it = s.lower_bound(make_pair(i,-1));
		long long low = prev(it)->second, high = it->second;
		while (high-low > 1) {
			long long mid = (low+high)/2;
			A.clear();
			for (long long i = 0; i < N; ++i) {
				long long a = lower_bound(dis.begin(),dis.end(),lst[i].second) - dis.begin();
				long long b = lower_bound(dis.begin(),dis.end(),lst[i].second-mid) - dis.begin();
				long long c = upper_bound(dis.begin(),dis.end(),lst[i].second+mid) - dis.begin() - 1;
				A.emplace_back(lst[i].first,0,a,0);
				A.emplace_back(lst[i].first-mid,-1,b,c);
				A.emplace_back(lst[i].first+mid,1,b,c);
			}
			sort(A.begin(),A.end());
			for (long long i = 0; i <= N; ++i) ft[i] = 0;
			long long ans = -N;
			for (auto x: A) {
				long long a,b,c,d; tie(a,b,c,d) = x;
				if (b == 0) ans += query(c);
				if (b == -1) update(c,1), update(d+1,-1);
				if (b == 1) update(c,-1), update(d+1,1);
			}
			s.emplace(ans/2,mid);
			if (ans/2 >= i) high = mid;
			else low = mid;
		}
		cout << high << '\n';
	}
	
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10066 ms 2124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10038 ms 39172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5975 ms 39072 KB Output is correct
2 Correct 6039 ms 39132 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 5700 ms 39152 KB Output is correct
5 Correct 4528 ms 39084 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5975 ms 39072 KB Output is correct
2 Correct 6039 ms 39132 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 5700 ms 39152 KB Output is correct
5 Correct 4528 ms 39084 KB Output is correct
6 Execution timed out 10025 ms 39132 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10066 ms 2124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10066 ms 2124 KB Time limit exceeded
2 Halted 0 ms 0 KB -