Submission #966637

#	Time	Username	Problem	Language	Result	Execution time	Memory
966637		emptypringlescan	New Home (APIO18_new_home)	C++17	57 / 100	5055 ms	313612 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define int long long
priority_queue<int> bruh[300005],del[300005];
int cnum;
struct node{
	int s,e,m;
	int val,pnum;
	node *l, *r;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		val=0;
		l=r=NULL;
		if(s==e){
			pnum=cnum;
			cnum++;
		}
	}
	
	void update(int S, int V, int R){
		if(s==e){
			if(R!=-1) del[pnum].push(R);
			if(V!=-1) bruh[pnum].push(V);
			while(!del[pnum].empty()&&!bruh[pnum].empty()&&bruh[pnum].top()==del[pnum].top()){
				bruh[pnum].pop();
				del[pnum].pop();
			}
			if(!bruh[pnum].empty()) val=bruh[pnum].top();
			else val=0;
			return;
		}
		if(S<=m){
			if(!l) l=new node(s,m);
			l->update(S,V,R);
		}
		else{
			if(!r) r=new node(m+1,e);
			r->update(S,V,R);
		}
		val=max((l?l->val:0),(r?r->val:0));
	}
	int query(int S){
		if(s==e) return val;
		if(S<=m) return (l?l->query(S):0);
		else return max((l?l->val:0),(r?r->query(S):0));
	}
} *root;
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,q,k;
    cin >> n >> k >> q;
    vector<pair<pair<int,int>,pair<int,int> > > up; //time,loc,type,+-1
    for(int i=0; i<n; i++){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		up.push_back({{c,a},{b,1}});
		up.push_back({{d+1,a},{b,-1}});
	}
	sort(up.begin(),up.end());
	root=new node(0,1e8+5);
	pair<pair<int,int>,int> qu[q]; //time,loc,index
	for(int i=0; i<q; i++){
		int a,b;
		cin >> a >> b;
		qu[i]={{b,a},i};
	}
	sort(qu,qu+q);
	multiset<int> occ[k+1];
	multiset<int>::iterator it;
	for(int i=1; i<=k; i++){
		occ[i].insert(0);
		occ[i].insert(1e16);
		root->update(0,1e16,-1);
	}
	int ans[q],cnt=0;
	for(int i=0; i<q; i++){
		while(cnt<(int)up.size()&&up[cnt].first.first<=qu[i].first.first){
			if(up[cnt].second.second==1){
				int t=up[cnt].second.first,p=up[cnt].first.second;
				it=occ[t].upper_bound(p);
				int nxt=*it;
				it--;
				int prv=*it;
				root->update(prv,p,nxt);
				root->update(p,nxt,-1);
				occ[t].insert(p);
			}
			else{
				int t=up[cnt].second.first,p=up[cnt].first.second;
				occ[t].erase(occ[t].find(p));
				it=occ[t].upper_bound(p);
				int nxt=*it;
				it--;
				int prv=*it;
				root->update(prv,nxt,p);
				root->update(p,-1,nxt);
			}
			cnt++;
		}
		int loc=qu[i].first.second;
		if(root->query(0)==1e16){
			ans[qu[i].second]=-1;
			continue;
		}
		int lo=0,hi=1e8,mid;
		while(lo<hi){
			mid=(lo+hi)/2;
			int big=root->query(max(loc-mid-1,0ll));
			if(big<=loc+mid) assert(big>=loc-mid),hi=mid;
			else lo=mid+1;
		}
		ans[qu[i].second]=lo;
	}
	for(int i=0; i<q; i++) cout << ans[i] << '\n';
}

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