oj.uz

Submission #439642

# Submission time Handle Problem Language Result Execution time Memory
439642 2021-06-30T12:14:47 Z ics0503 Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 28628 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct xy { long long x, y, idx; }a[262626];
bool sort_x(xy a, xy b) {
	if (a.x != b.x)return a.x < b.x;
	return a.y < b.y;
}
bool sort_y(xy a, xy b) {
	if (a.y != b.y)return a.y > b.y;
	return a.x > b.x;
}
long long T[2][1212121], TW[2][1212121], tn;
void insert_g(long long type, long long w, long long g) {
	T[type][tn + w] = g;
	TW[type][tn + w] = tn+w;
	for (long long i = (w + tn) / 2; i > 0; i /= 2) {
		T[type][i] = min(T[type][i * 2], T[type][i * 2 + 1]);
		TW[type][i] = T[type][i * 2] <= T[type][i * 2 + 1] ? TW[type][i * 2] : TW[type][i * 2 + 1];
	}
}
long long n, k, mxv = 1e18;
pair<long long, long long>search_g(long long type, long long s, long long e) {
	s += tn; e += tn;
	pair<long long, long long>res;
	res.first = mxv;
	while (s <= e) {
		if (s % 2 == 1) {
			if (res.first > T[type][s])res = { T[type][s],TW[type][s] };
			s++;
		}
		if (e % 2 == 0) {
			if (res.first > T[type][e])res = { T[type][e],TW[type][e] };
			e--;
		}
		s /= 2; e /= 2;
	}
	return res;
}
vector<long long>dd;
long long f(long long x, long long flag) {
	long long i, j, pc;
	vector<pair<long long, long long>>L, R;
	for (i = 0; i < tn * 2; i++)T[0][i] = T[1][i] = mxv;
	pc = 0; long long ans = 0;
	for (i = 0; i < n; i++) {
		while (pc < k) {
			auto sr = search_g(0, a[i].idx, n);
			long long v = sr.first, who = sr.second - tn;
			if (v == mxv)break;
			long long res = v - a[i].x - a[i].y;
			if (res > x)break;
			if (flag) dd.push_back(res);
			L.push_back({ v,who }); insert_g(0, who, mxv);
			ans += res; pc++;
		}
		while (pc < k) {
			auto sr = search_g(1, 0, a[i].idx);
			long long v = sr.first, who = sr.second - tn;
			if (v == mxv)break;
			long long res = v + a[i].x - a[i].y;
			if (res > x)break;
			if (flag) dd.push_back(res);
			R.push_back({ v,who }); insert_g(1, who, mxv);
			ans += res; pc++;
		}
		for (auto v : L)insert_g(0, v.second, v.first);
		for (auto v : R)insert_g(1, v.second, v.first);
		L.clear(); R.clear();
		insert_g(0, a[i].idx, a[i].x + a[i].y);
		insert_g(1, a[i].idx, -a[i].x + a[i].y);
	}
	if (pc < k)return -1;
	return ans;
}

int main() {
	scanf("%lld%lld", &n, &k);
	for (tn = 1; tn <= n; tn *= 2);
	long long i, j;
	for (i = 0; i < n; i++)scanf("%lld%lld", &a[i].x, &a[i].y);
	sort(a, a + n, sort_x);
	for (i = 0; i < n; i++)a[i].idx = i;
	sort(a, a + n, sort_y);
	long long s = 1, e = 1e10, ans = 0;
	while (s <= e) {
		long long m = (s + e) / 2;
		long long R = f(m, 0);
		if (R == -1) {
			s = m + 1;
		}
		else {
			e = m - 1;
			ans = m;
		}
	}
	f(ans - 1, 1);
	sort(dd.begin(), dd.end());
	for (auto v : dd)printf("%lld\n", v);
	for (i = dd.size(); i < k; i++)printf("%lld\n", ans);
	return 0;
}

Compilation message

road_construction.cpp: In function 'long long int f(long long int, long long int)':
road_construction.cpp:43:15: warning: unused variable 'j' [-Wunused-variable]
   43 |  long long i, j, pc;
      |               ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:81:15: warning: unused variable 'j' [-Wunused-variable]
   81 |  long long i, j;
      |               ^
road_construction.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  scanf("%lld%lld", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
road_construction.cpp:82:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  for (i = 0; i < n; i++)scanf("%lld%lld", &a[i].x, &a[i].y);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1576 ms 5020 KB Output is correct
2 Correct 1544 ms 5076 KB Output is correct
3 Correct 1468 ms 5048 KB Output is correct
4 Correct 1375 ms 5112 KB Output is correct
5 Correct 1408 ms 4052 KB Output is correct
6 Correct 16 ms 332 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4484 ms 28540 KB Output is correct
2 Correct 4347 ms 28536 KB Output is correct
3 Correct 1199 ms 5132 KB Output is correct
4 Correct 3784 ms 28320 KB Output is correct
5 Correct 4331 ms 28528 KB Output is correct
6 Correct 4275 ms 28628 KB Output is correct
7 Correct 4096 ms 27980 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6535 ms 27336 KB Output is correct
2 Correct 6101 ms 27336 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1958 ms 25156 KB Output is correct
5 Correct 3585 ms 27588 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6535 ms 27336 KB Output is correct
2 Correct 6101 ms 27336 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1958 ms 25156 KB Output is correct
5 Correct 3585 ms 27588 KB Output is correct
6 Correct 6833 ms 27328 KB Output is correct
7 Correct 7044 ms 27336 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 7223 ms 27336 KB Output is correct
11 Correct 1938 ms 25184 KB Output is correct
12 Correct 3811 ms 27484 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1576 ms 5020 KB Output is correct
2 Correct 1544 ms 5076 KB Output is correct
3 Correct 1468 ms 5048 KB Output is correct
4 Correct 1375 ms 5112 KB Output is correct
5 Correct 1408 ms 4052 KB Output is correct
6 Correct 16 ms 332 KB Output is correct
7 Correct 5114 ms 15976 KB Output is correct
8 Correct 5031 ms 15984 KB Output is correct
9 Correct 1357 ms 5160 KB Output is correct
10 Correct 4304 ms 15272 KB Output is correct
11 Correct 4019 ms 15236 KB Output is correct
12 Correct 3197 ms 13932 KB Output is correct
13 Correct 4030 ms 14664 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1576 ms 5020 KB Output is correct
2 Correct 1544 ms 5076 KB Output is correct
3 Correct 1468 ms 5048 KB Output is correct
4 Correct 1375 ms 5112 KB Output is correct
5 Correct 1408 ms 4052 KB Output is correct
6 Correct 16 ms 332 KB Output is correct
7 Correct 4484 ms 28540 KB Output is correct
8 Correct 4347 ms 28536 KB Output is correct
9 Correct 1199 ms 5132 KB Output is correct
10 Correct 3784 ms 28320 KB Output is correct
11 Correct 4331 ms 28528 KB Output is correct
12 Correct 4275 ms 28628 KB Output is correct
13 Correct 4096 ms 27980 KB Output is correct
14 Correct 6535 ms 27336 KB Output is correct
15 Correct 6101 ms 27336 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1958 ms 25156 KB Output is correct
18 Correct 3585 ms 27588 KB Output is correct
19 Correct 6833 ms 27328 KB Output is correct
20 Correct 7044 ms 27336 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 292 KB Output is correct
23 Correct 7223 ms 27336 KB Output is correct
24 Correct 1938 ms 25184 KB Output is correct
25 Correct 3811 ms 27484 KB Output is correct
26 Correct 5114 ms 15976 KB Output is correct
27 Correct 5031 ms 15984 KB Output is correct
28 Correct 1357 ms 5160 KB Output is correct
29 Correct 4304 ms 15272 KB Output is correct
30 Correct 4019 ms 15236 KB Output is correct
31 Correct 3197 ms 13932 KB Output is correct
32 Correct 4030 ms 14664 KB Output is correct
33 Execution timed out 10079 ms 27400 KB Time limit exceeded
34 Halted 0 ms 0 KB -