Submission #203718

#	Time	Username	Problem	Language	Result	Execution time	Memory
203718		Segtree	New Home (APIO18_new_home)	C++14	12 / 100	2393 ms	100936 KiB

new_home

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 60010
ll n,q,k;
ll fans[N];
multiset<ll> s[410];
struct st{
	ll tim,x,col,typ;
	bool operator<(const st&key)const{
		if(this->tim==key.tim)return this->typ<key.typ;
		return this->tim<key.tim;
	}
};
int main(){
	cin>>n>>k>>q;
	vector<st> v;
	rep(i,n){
		ll x,col,a,b; cin>>x>>col>>a>>b; col--;
		v.push_back((struct st){a,x,col,0});
		v.push_back((struct st){b,x,col,2});
	}
	rep(i,q){
		ll l,y; cin>>l>>y;
		v.push_back((struct st){y,l,i,1});
	}
	sort(v.begin(),v.end());
	rep(i,k){
		s[i].insert(-1);
		s[i].insert(2e8);
	}
	for(auto e:v){
		if(e.typ==0){
			s[e.col].insert(e.x);
		}
		if(e.typ==1){
			ll ans=0;
			rep(i,k){
				ll mi=1e17;
				auto it=s[i].lower_bound(e.x);
				if(*it<2e8)chmin(mi,*it-e.x);
				it--;
				if(*it>-1)chmin(mi,e.x-*it);
				chmax(ans,mi);
			}
			if(ans==1e17)ans=-1;
			fans[e.col]=ans;
		}
		if(e.typ==2){
			s[e.col].erase(s[e.col].find(e.x));
		}
	}
	rep(i,q)cout<<fans[i]<<endl;
}

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