Submission #1123490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123490		sixiyo7205	New Home (APIO18_new_home)	C++20	12 / 100	1686 ms	23964 KiB

new_home

//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#define ll long long
#define pir pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn = 3e5 + 5;

template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;}
template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;}

struct SHOP{
	int x = 0,t = 0,y1 = 0,y2 = 0;
};

SHOP a[maxn];
pir Q[maxn];

void input(int n,int k,int q){
	for (int i = 1 ; i <= n ; i++){
		cin >> a[i].x >> a[i].t >> a[i].y1 >> a[i].y2;
	}
	
	for (int i = 1 ; i <= q ; i++)
	   cin >> Q[i].fi >> Q[i].se;
}

namespace subtask1{
	bool subtask1(int n,int k,int q){
		return (max(n,q) <= 400); 
	}
	
	bool satisfy(const vector <SHOP> shop,int k){
		if (!shop.size()) return 0;
		if (shop[0].t > 1) return 0;
		if (shop.back().t < k) return 0;
		
		for (int i = 1 ; i < shop.size() ; i++)
		    if (abs(shop[i].t - shop[i - 1].t) > 1) return 0;
		return 1;
	}
	
	int answer_query(int x,int y,int k,int n){
		vector <SHOP> shop;
		for (int i = 1 ; i <= n ; i++)
		    if (a[i].y1 <= y && y <= a[i].y2)
		        shop.push_back(a[i]);
		
		//absence of type
		if (!satisfy(shop,k)) return -1;
		
		int res = 0,p = 0;
		while (p < shop.size()){
			int nxt = p,dist = abs(shop[p].x - x);
			while (nxt < shop.size() && shop[p].t == shop[nxt].t) nxt++;
			
			for (int i = p ; i < nxt ; i++)
			    dist = min(dist,abs(shop[i].x - x));
			
			maxi(res,dist);
			p = nxt;
		}
		return res;
	}
	
	inline bool by_type(const SHOP &x,const SHOP &y){
		return (x.t < y.t);
	}
	void solve(int n,int k,int q){
		sort(a + 1,a + 1 + n,by_type);
		
		for (int i = 1 ; i <= q ; i++){
			int x = Q[i].fi,y = Q[i].se;
			
			cout << answer_query(x,y,k,n) << "\n";
		}
	}
}

namespace subtask2{
	bool subtask2(int n,int k,int q){
		return (q <= 60000) && (k <= 400);	
	}
	
	struct sweepline{
		int x = 0,y = 0,t = 0,T = 0;
		
		bool operator <(const sweepline&other) const{
			return (y < other.y) || (y == other.y && T < other.T);
		}
	};
	
	const int MAXK = 406;
	
	multiset <int> s[MAXK];
	int res[maxn];
	vector <sweepline> event;
	
	void generate_event(int n,int k,int q){
		for (int i = 1 ; i <= n ; i++){
			event.push_back({a[i].x,a[i].y1,a[i].t,0});
			event.push_back({a[i].x,a[i].y2,a[i].t,2});
		}
		
		for (int i = 1 ; i <= q ; i++)
		    event.push_back({Q[i].fi,Q[i].se,i,1});
		
		sort(event.begin(),event.end());
	}
	
	void modify_location(int x,int t,int T){
		if (!T) s[t].insert(x);
		if (T == 2) s[t].erase(s[t].find(x));
	}
	
	int answer_query(int x,int k){
		for (int i = 1 ; i <= k ; i++)
		    if (!s[i].size()) return -1;
		
		int f = 0;
		for (int i = 1 ; i <= k ; i++){
			if ((*s[i].rbegin()) < x){
				maxi(f,x - (*s[i].rbegin()));
				continue;
			}
			
			set <int>::iterator it = s[i].lower_bound(x);
			int x1 = (*it),x2 = x1;
			
			if (it != s[i].begin()) x2 = (*prev(it));
			
			maxi(f,min(abs(x1 - x),abs(x2 - x)));
		}
		
		return f;
	}
	
	void solve(int n,int k,int q){
		generate_event(n,k,q);
		
		for (sweepline t : event){
			int T = t.T;
			
			if (T == 0 || T == 2)
			    modify_location(t.x,t.t,t.T);
			
			if (T == 1)
			   res[t.t] = answer_query(t.x,k);
		}
		
		for (int i = 1 ; i <= q ; i++) cout << res[i] << "\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
//	freopen("NEWHOME.inp","r",stdin);
//	freopen("NEWHOME.out","w",stdout);
	
	int n,k,q;
	cin >> n >> k >> q;
	input(n,k,q);
	
	if (subtask1::subtask1(n,k,q)){
		subtask1::solve(n,k,q);
		return 0;
	}
	
	
	subtask2::solve(n,k,q);
	
	

	return 0;
}

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