Submission #1111655

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1111655	2024-11-12T13:31:48 Z	Onur_Ilgaz	New Home (APIO18_new_home)	C++17	10 / 100	208 ms	35496 KB

new_home

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;

int32_t main(){
	fast
	int n, k, q;
	cin >> n >> k >> q;
	vector <pair<int, int> > arr, ranges;
	for(int i = 0; i < n; i++) {
		int x, t, a, b;
		cin >> x >> t >> a >> b;
		arr.push_back({x, t});
	}
	sort(arr.begin(), arr.end());
	int l = 0, r = -1, cnt = 0;
	vector <int> have(k + 1);
	while(r < n - 1) {
		r++;
		auto [pos, type] = arr[r];
		if(!have[type]) cnt++;
		have[type]++;
		while(cnt == k) {
			auto [tpos, ttype] = arr[l];
			have[ttype]--;
			if(!have[ttype]) cnt--;
			// add to ranges
			ranges.push_back({tpos, pos});
			l++;
		}
	}
	// for(auto it:ranges) {
	// 	cout << it.first << ' ' << it.second << '\n';
	// }
	if(ranges.empty()) {
		for(int i = 0; i < q; i++) {
			cout << -1 << "\n";
		}
		return 0;
	}
	vector <pair<int, int> > qq;
	for(int i = 0; i < q; i++) {
		int x, t;
		cin >> x >> t;
		qq.push_back({x, i});
	}
	sort(qq.begin(), qq.end());
	vector <int> ans(q);
	auto calc = [&](int rind, int pos) {
		if(rind == ranges.size()) return inf;
		auto [l, r] = ranges[rind];
		return max(abs(pos - l), abs(pos - r));
	};
	int now = 0;
	for(auto [pos, ans_ind] : qq) {
		while(calc(now + 1, pos) <= calc(now, pos)) {
			now++;
		}
		ans[ans_ind] = calc(now, pos);
	}
	for(auto it:ans) {
		cout << it << "\n";
	}
}

Compilation message

new_home.cpp: In lambda function:
new_home.cpp:52:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   if(rind == ranges.size()) return inf;
      |      ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Incorrect	1 ms	336 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Incorrect	1 ms	336 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	198 ms	20792 KB	Output is correct
2	Correct	203 ms	31252 KB	Output is correct
3	Correct	207 ms	34712 KB	Output is correct
4	Correct	192 ms	31412 KB	Output is correct
5	Correct	199 ms	34076 KB	Output is correct
6	Correct	202 ms	34076 KB	Output is correct
7	Correct	195 ms	32940 KB	Output is correct
8	Correct	201 ms	31396 KB	Output is correct
9	Correct	208 ms	35496 KB	Output is correct
10	Correct	192 ms	34720 KB	Output is correct
11	Correct	172 ms	33828 KB	Output is correct
12	Correct	181 ms	34588 KB	Output is correct