Submission #401867

#	Time	Username	Problem	Language	Result	Execution time	Memory
401867		faresbasbs	New Home (APIO18_new_home)	C++14	5 / 100	5059 ms	1048580 KiB

new_home

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

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

struct node{
	int l,r,cnt;
	node *lc,*rc;
	node(){
		l = r = cnt = 0;
		lc = rc = NULL;
	}
};

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

void del2(node *curr , int val){
	while(curr->l != curr->r){
		int mid = (curr->l+curr->r)/2;
		if(val <= mid){
			curr = curr->lc;
		}else{
			curr = curr->rc;
		}
		curr->cnt -= 1;
	}
}

void del(int curr , int val){
	while(curr){
		del2(segment[curr],val);
		curr /= 2;
	}
}

void add2(node *curr , int val){
	while(curr->l != curr->r){
		int mid = (curr->l+curr->r)/2;
		if(val <= mid){
			if(curr->lc == NULL){
				curr->lc = new node();
				curr->lc->l = curr->l , curr->lc->r = mid;
			}
			curr = curr->lc;
		}else{
			if(curr->rc == NULL){
				curr->rc = new node();
				curr->rc->l = mid+1 , curr->rc->r = curr->r;
			}
			curr = curr->rc;
		}
		curr->cnt += 1;
	}
}

void add(int curr , int val){
	while(curr){
		if(segment[curr] == NULL){
			segment[curr] = new node();
			segment[curr]->l = 1 , segment[curr]->r = t;
		}
		add2(segment[curr],val);
		curr /= 2;
	}
}

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

int num2(int a , int b , node *curr , int l , int r){
	if(b < l || a > r || curr == NULL){
		return 0;
	}
	if(a <= l && b >= r){
		return curr->cnt;
	}
	int mid = (l+r)/2;
	return num2(a,b,curr->lc,l,mid)+num2(a,b,curr->rc,mid+1,r);
}

int num(int a , int b , int curr , int l , int r){
	if(b < l || a > r){
		return 0;
	}
	if(a <= l && b >= r){
		if(segment[curr] == NULL){
			return 0;
		}
		return num2(b+1,t,segment[curr],1,t);
	}
	int mid = (l+r)/2;
	return num(a,b,2*curr,l,mid)+num(a,b,2*curr+1,mid+1,r);
}

int main(){
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	cin >> n >> k >> q;
	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());
	t = pow(2,ceil(log2(all.size()+1)));
	for(int i = 1 ; i <= k ; i += 1){
		ms[i].insert(all.size()+1);
	}
	segment.resize(2*t);
	sort(qs.begin(),qs.end());
	for(auto i : qs){
		if(i.type > k){
			i.type -= k;
			if(num(1,all.size(),1,1,t) < 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(val1,val2,1,1,t) >= 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+t-1,val);
			if(it != ms[i.type].begin()){
				it--;
				int pos = *it;
				del(pos+t-1,val) , add(pos+t-1,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+t-1,val);
			if(it != ms[i.type].begin()){
				it--;
				int pos = *it;
				del(pos+t-1,i.x) , add(pos+t-1,val);
			}
		}
	}
	for(int i = 1 ; i <= q ; i += 1){
		cout << ans[i] << '\n';
	}
}

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