Submission #673286

#	Time	Username	Problem	Language	Result	Execution time	Memory
673286		Dan4Life	New Home (APIO18_new_home)	C++17	12 / 100	5025 ms	83816 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long 
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
using ll = long long;
const int maxn = (int)3e5+10;
const ll LINF = (ll)2e18;
struct store{
	int x, t, a, b;
};

struct query{
	int x, y, i;
};

int n, k, q;
int ans[maxn];
vector<store> v;
vector<query> Q;
vector<int> cord;
unordered_map<int,int> ind;

int32_t main(){
	cin >> n >> k >> q; v.resize(n); Q.resize(q); int cnt = 0;
	for(int i = 0; i < n; i++){
		cin >> v[i].x >> v[i].t >> v[i].a >> v[i].b;
		cord.pb(v[i].a), cord.pb(v[i].b);
	}
	for(int i = 0; i < q; i++){
		cin >> Q[i].x >> Q[i].y; Q[i].i=i;
		cord.pb(Q[i].y);
	}
	sort(all(cord)); cord.erase(unique(all(cord)),cord.end());
	for(auto u : cord) ind[u]=cnt++;
	for(auto &u : v) u.a=ind[u.a], u.b=ind[u.b];
	for(auto &u : Q) u.y=ind[u.y];
	sort(all(v), [&](store a, store b){
		if(a.a!=b.a) return a.a < b.a;
		if(a.b!=b.b) return a.b < b.b;
		if(a.x!=b.x) return a.x < b.x;
		return a.t < b.t;
	});
	sort(all(Q), [&](query a, query b){
		if(a.y!=b.y) return a.y < b.y;
		if(a.x!=b.x) return a.x < b.x;
		return a.i < b.i;
	});
	int i = 0, j = 0;
	multiset<int> S[k+1];
	set<pair<int,int>> cur;
	for(int Time = 0; Time < cnt; Time++){
		while(i < sz(v) and v[i].a==Time){
			S[v[i].t].insert(v[i].x); 
			cur.insert({v[i].b,i}); i++;
		}
		while(j < sz(Q) and Q[j].y==Time){
			for(int l = 1; l <= k; l++){
				if(S[l].empty()){ans[Q[j].i]=-1; break;}
				auto itr = S[l].lower_bound(Q[j].x);
				auto itr2 = itr; if(itr2!=S[l].begin()) itr2--;
				int dis = LINF;
				if(itr!=S[l].end()) dis = min(dis, abs(*itr-Q[j].x));
				if(itr2!=S[l].end()) dis = min(dis, abs(*itr2-Q[j].x));
				ans[Q[j].i] = max(ans[Q[j].i], dis);
			}
			j++;
		}
		while(!cur.empty()){
			auto itr = cur.begin(); int i = itr->se;
			if(itr->fi==Time){
				S[v[i].t].erase(S[v[i].t].find(v[i].x));
				cur.erase(cur.begin());
			}
			else break;
		}
	}
	for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}
/*
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
*/

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