Submission #745018

#	Time	Username	Problem	Language	Result	Execution time	Memory
745018		b00norp	New Home (APIO18_new_home)	C++14	5 / 100	5090 ms	15240 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e18;

bool cmp(array<int, 4> a, array<int, 4> b)
{
	if(a[0] == b[0])
	{
		return a[3] < b[3];
	}
	return a[0] < b[0];
}

void Solve() 
{
	int n, k, q;
	cin >> n >> k >> q;
	vector<array<int, 4> > stores(n);
	for(int i = 0; i < n; i++)
	{
		cin >> stores[i][0] >> stores[i][1] >> stores[i][2] >> stores[i][3];
	}	
	vector<array<int, 2> > queries(q);
	for(int i = 0; i < q; i++)
	{
		cin >> queries[i][0] >> queries[i][1];
		// cout << "query(" << queries[i][0] << ", " << queries[i][1] << ")\n";
		vector<int> res(k + 1, INF);
		for(int j = 0; j < n; j++)
		{
			// cout << "store(x, type, a, b) = " << "store(" << stores[j][0] << ", " << stores[j][1] << ", " << stores[j][2] << ", " << stores[j][3] << ")\n";
			if(stores[j][2] > queries[i][1] or stores[j][3] < queries[i][1])
			{
				continue;
			}
			res[stores[j][1]] = min(res[stores[j][1]], abs(queries[i][0] - stores[j][0]));
			// cout << "type = " << stores[j][1] << ", result = " << res[stores[j][1]] << "\n";
		}
		int ans = 0;
		for(int j = 1; j <= k; j++)
		{
			ans = max(ans, res[j]);
		}
		ans = (ans == INF) ? -1 : ans;
		cout << ans << "\n";
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    //cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

/*
Sample 1:
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

Sample 2:
2 1 3
1 1 1 4
1 1 2 6 
1 3
1 5
1 7

Sample 3:
1 1 1
100000000 1 1 1
1 1

*/

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20