oj.uz

Submission #439643

# Submission time Handle Problem Language Result Execution time Memory
439643 2021-06-30T12:18:42 Z ics0503 Road Construction (JOI21_road_construction) C++17
0 / 100
 10000 ms 13592 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct xy { int 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;
}
int T[2][1212121], TW[2][1212121], tn;
void insert_g(int type, int w, int g) {
	T[type][tn + w] = g;
	TW[type][tn + w] = tn+w;
	for (int 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];
	}
}
int n, k, mxv = 2e9;
pair<int, int>search_g(int type, int s, int e) {
	s += tn; e += tn;
	pair<int, int>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<int>dd;
int f(int x, int flag) {
	int i, j, pc;
	vector<pair<int, int>>L, R;
	for (i = 0; i < tn * 2; i++)T[0][i] = T[1][i] = mxv;
	pc = 0; int ans = 0;
	for (i = 0; i < n; i++) {
		while (pc < k) {
			auto sr = search_g(0, a[i].idx, n);
			int v = sr.first, who = sr.second - tn;
			if (v == mxv)break;
			int 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);
			int v = sr.first, who = sr.second - tn;
			if (v == mxv)break;
			int 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 1;
}

int main() {
	scanf("%d%d", &n, &k);
	for (tn = 1; tn <= n; tn *= 2);
	int i, j;
	for (i = 0; i < n; i++)scanf("%d%d", &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);
	int s = 1, e = 2e9, ans = 0;
	while (s <= e) {
		int m = (s + e) / 2;
		int 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("%d\n", v);
	for (i = dd.size(); i < k; i++)printf("%d\n", ans);
	return 0;
}

Compilation message

road_construction.cpp: In function 'int f(int, int)':
road_construction.cpp:43:9: warning: unused variable 'j' [-Wunused-variable]
   43 |  int i, j, pc;
      |         ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:81:9: warning: unused variable 'j' [-Wunused-variable]
   81 |  int 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("%d%d", &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("%d%d", &a[i].x, &a[i].y);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3913 ms 13580 KB Output is correct
2 Correct 3896 ms 13592 KB Output is correct
3 Execution timed out 10093 ms 332 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4976 ms 11288 KB Output is correct
2 Correct 4911 ms 11292 KB Output is correct
3 Execution timed out 10040 ms 204 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4976 ms 11288 KB Output is correct
2 Correct 4911 ms 11292 KB Output is correct
3 Execution timed out 10040 ms 204 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10097 ms 332 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 10097 ms 332 KB Time limit exceeded
2 Halted 0 ms 0 KB -