Submission #745022

#	Time	Username	Problem	Language	Result	Execution time	Memory
745022		b00norp	New Home (APIO18_new_home)	C++14	5 / 100	5064 ms	97132 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, 3> > stores[k + 1];
	map<int, int> mp;
	for(int i = 1; i <= n; i++)
	{
		int x, type, st, fi;
		cin >> x >> type >> st >> fi;
		fi += 1;
		stores[type].push_back({x, st, fi});
		mp[st]++;
		mp[fi]++;
	}	
	vector<array<int, 2> > queries(q);
	for(int i = 0; i < q; i++)
	{
		cin >> queries[i][0] >> queries[i][1];
		mp[queries[i][1]]++;
	}
	int cnt = 1;
	for(auto i: mp)
	{
		mp[i.first] = cnt++;
	}
	vector<array<int, 4> > chronological_order;
	for(int i = 1; i <= k; i++)
	{
		for(auto [x, st, fi]: stores[i])
		{
			st = mp[st];
			fi = mp[fi];
			chronological_order.push_back({st, i, x, 0});
			chronological_order.push_back({fi, -i, x, 0});
		}
	}
	cnt = 0;
	for(auto [x, year]: queries)
	{
		year = mp[year];
		chronological_order.push_back({year, cnt++, x, 1});
	}
	sort(chronological_order.begin(), chronological_order.end(), cmp);
	multiset<int> opened_shops[k + 1];
	vector<int> res(q);
	for(auto [year, idx, x, type]: chronological_order)
	{
		if(type == 0)
		{
			if(idx < 0)
			{
				idx = -idx;
				opened_shops[idx].erase(opened_shops[idx].find(x));
			}
			else
			{
				opened_shops[idx].insert(x);
			}
		}
		else
		{
			int ans = 0;
			for(int i = 1; i <= k; i++)
			{
				if(opened_shops[i].size() == 0)
				{
					ans = -1;
					break;
				}
				auto it = lower_bound(opened_shops[i].begin(), opened_shops[i].end(), x);
				int cur_ans = 1e18;
				if(it != opened_shops[i].end())
				{
					cur_ans = min(cur_ans, abs(*(it) - x));
				}
				if(it != opened_shops[i].begin())
				{
					it = prev(it);
				}
				cur_ans = min(cur_ans, abs(*(it) - x));
				ans = max(ans, cur_ans);
			}
			res[idx] = ans;
		}
	}
	for(int i = 0; i < q; i++)
	{
		cout << res[i] << "\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

*/

Compilation message (stderr)

new_home.cpp: In function 'void Solve()':
new_home.cpp:47:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |   for(auto [x, st, fi]: stores[i])
      |            ^
new_home.cpp:56:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |  for(auto [x, year]: queries)
      |           ^
new_home.cpp:64:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |  for(auto [year, idx, x, type]: chronological_order)
      |           ^

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