Submission #401873

#	Time	Username	Problem	Language	Result	Execution time	Memory
401873		faresbasbs	New Home (APIO18_new_home)	C++14	47 / 100	5097 ms	232884 KiB

new_home

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

struct query{
	int x,t,type;
	bool operator <(query b) const{
		if(t == b.t){
			return type < b.type;
		}
		return t < b.t;
	}
};

vector<ordered_set> segment;
int n,N,q,k,t,ans[300001];
multiset<int> ms[300001];
vector<query> qs;
vector<int> all;

void del(int curr , int val){
	for( ; curr <= N ; curr += curr&(-curr)){
		segment[curr].erase(segment[curr].find_by_order(segment[curr].order_of_key(val)));
	}
}

void add(int curr , int val){
	for( ; curr <= N ; curr += curr&(-curr)){
		segment[curr].insert(val);
	}
}

int cmp(int val){
	return lower_bound(all.begin(),all.end(),val)-all.begin()+1;
}

int num(int curr , int val){
	int ret = 0;
	for( ; curr ; curr -= curr&(-curr)){
		ret += segment[curr].size()-segment[curr].order_of_key(val);
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	cin >> n >> k >> q;
	for(int i = 1 ; i <= k ; i += 1){
		ms[i].insert(100000001);
	}
	for(int i = 0 ; i < n ; i += 1){
		int x,t,a,b;
		cin >> x >> t >> a >> b;
		all.push_back(x);
		qs.push_back({x,a,t});
		qs.push_back({x,b+1,-t});
	}
	for(int i = 1 ; i <= q ; i += 1){
		int l,y;
		cin >> l >> y;
		all.push_back(l);
		qs.push_back({l,y,k+i});
	}
	sort(all.begin(),all.end());
	all.erase(unique(all.begin(),all.end()),all.end());
	segment.resize(all.size()+1);
	sort(qs.begin(),qs.end());
	N = all.size();
	for(auto i : qs){
		if(i.type > k){
			i.type -= k;
			if(num(N,N+1) < k){
				ans[i.type] = -1;
				continue;
			}
			int first = -1 , last = 100000000;
			while(last-first > 1){
				int mid = (first+last)/2 , val1 = lower_bound(all.begin(),all.end(),i.x-mid)-all.begin()+1;
				int val2 = upper_bound(all.begin(),all.end(),i.x+mid)-all.begin();
				if(num(val2,val2+1)-num(val1-1,val2+1) >= k){
					last = mid;
				}else{
					first = mid;
				}
			}
			ans[i.type] = last;
		}else if(i.type > 0){
			i.x = cmp(i.x);
			auto it = ms[i.type].lower_bound(i.x);
			int val = *it;
			add(i.x,val);
			if(it != ms[i.type].begin()){
				it--;
				int pos = *it;
				del(pos,val) , add(pos,i.x);
			}
			ms[i.type].insert(i.x);
		}else{
			i.x = cmp(i.x);
			i.type = -i.type;
			ms[i.type].erase(ms[i.type].find(i.x));
			auto it = ms[i.type].lower_bound(i.x);
			int val = *it;
			del(i.x,val);
			if(it != ms[i.type].begin()){
				it--;
				int pos = *it;
				del(pos,i.x) , add(pos,val);
			}
		}
	}
	for(int i = 1 ; i <= q ; i += 1){
		cout << ans[i] << '\n';
	}
}

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