oj.uz

Submission #406180

# Submission time Handle Problem Language Result Execution time Memory
406180 2021-05-17T09:06:31 Z kshitij_sodani New Home (APIO18_new_home) C++14
0 / 100
 5000 ms 672328 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
int n,k,q;
int ans[300001];
set<int> pre[300001];
map<int,int> pre2[300001];
bool vis[3000001];
map<pair<int,pair<int,int>>,int> xx;
map<pair<int,pair<int,int>>,int> xx2;
map<int,int> ss;
map<int,int> ss2;
vector<pair<int,int>> yy;

int ne=0;
int nn;
pair<int,int> solve(int i,int j){
	pair<int,int> ac={i,0};
	pair<int,int> ac2={j+1,0};
	return {lower_bound(yy.begin(),yy.end(),ac)-yy.begin(),lower_bound(yy.begin(),yy.end(),ac2)-yy.begin()-1};
}
priority_queue<pair<int,int>> tree[4*800001];
priority_queue<pair<int,int>> tree2[4*800001];
int kk=1;
//int ans[300001];
void update(int no,int l,int r,int aa,int bb,pair<int,int> x,int st){
	/*if(no==0){
		cout<<aa<<":"<<bb<<":"<<x.a<<":"<<x.b<<endl;
	}*/
	
	if(r<aa or l>bb){
		return;
	}
	if(aa<=l and r<=bb){
		//cout<<l<<",,"<<r<<endl;
		if(kk){
			if(tree[no].size()){
				pair<int,int> ma=tree[no].top();
				tree[no].pop();
				tree[no].push(max(ma,x));
				 ma=tree2[no].top();
				tree2[no].pop();
				tree2[no].push(max(ma,{-x.a,x.b}));
			}
			else{
				tree[no].push(x);

				tree2[no].push({-x.a,x.b});

			}
			return ;
		}
		tree[no].push(x);

		tree2[no].push({-x.a,x.b});


	}
	else{
		int mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,x,st);
		update(no*2+2,mid+1,r,aa,bb,x,st);
	}
}
int query(int no,int l,int r,int i){
	int cur=0;
	while(tree[no].size()){
		if(vis[(tree[no].top()).b]){
			tree[no].pop();

		}
		else{
			break;
		}
	}
	while(tree2[no].size()){
		if(vis[(tree2[no].top()).b]){
			tree2[no].pop();
			
		}
		else{
			break;
		}
	}

	if(tree[no].size()){
		//cout<<l<<","<<r<<","<<yy[i].a<<endl;
		cur=max(cur,abs((tree[no].top()).a-yy[i].a));
		
		cur=max(cur,abs(-(tree2[no].top()).a-yy[i].a));
	}
	if(l<r){
		int mid=(l+r)/2;
		if(i<=mid){
			cur=max(cur,query(no*2+1,l,mid,i));
		}
		else{
			cur=max(cur,query(no*2+2,mid+1,r,i));
		}
	}
	return cur;

}
void add(int i,int aa,int bb,int st){
	int mid=(aa+bb)/2;
	if(st==1){
		xx[{i,{aa,mid}}]=ne;
		
		pair<int,int> ind=solve(aa,mid);

		update(0,0,nn-1,ind.a,ind.b,{aa,ne},0);
		ne++;
		xx[{i,{mid+1,bb}}]=ne;
		ind=solve(mid+1,bb);
		update(0,0,nn-1,ind.a,ind.b,{bb,ne},1);
		ne++;
	}
	else{
		vis[xx[{i,{aa,mid}}]]=1;
		vis[xx[{i,{mid+1,bb}}]]=1;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k>>q;

	vector<pair<pair<int,int>,pair<int,int>>> cur;
	for(int i=0;i<n;i++){
		int x,aa,bb,tt;
		cin>>x>>tt>>aa>>bb;
		ss[x]++;
		tt--;
		if(aa!=1 or bb!=1e8){
			kk=0;
		}
		cur.pb({{aa,-1},{x,tt}});
		cur.pb({{bb,1},{x,tt}});
	}
	for(int i=0;i<q;i++){
		int x,aa;
		cin>>x>>aa;
		ss[x]++;
		cur.pb({{aa,0},{x,i}});
	}
	sort(cur.begin(),cur.end());
	int ind5=-1;
	
	ss[-2e8]++;
	
	ss[2e8]++;
	for(auto j:ss){
		ind5++;
		ss2[j.a]=ind5;
		yy.pb({j.a,ind5});
	}
	nn=yy.size();
	//sort(cur.begin(),cur.end());
/*	for(auto j:yy){
		cout<<j.a<<",";
	}
	cout<<endl;*/
	
	for(int i=0;i<k;i++){
		pre[i].insert(-2e8);
		pre2[i][-2e8]++;
		pre[i].insert(2e8);
		pre2[i][2e8]++;
		add(i,-2e8,2e8,1);
	//	xx[{i,{-2e8,2e8}}]=;
	//	update(0,0,nn-1,0,nn-1);
	}

	for(auto j:cur){
		if(j.a.b==-1){
			//add
			//continue;
			if(pre2[j.b.b].find(j.b.a)!=pre2[j.b.b].end()){
				if(pre2[j.b.b][j.b.a]>0){
					pre2[j.b.b][j.b.a]++;
					continue;
				}
			}
			//else{
				pre2[j.b.b][j.b.a]++;
				int re=*(pre[j.b.b].lower_bound(j.b.a));
				auto jj=pre[j.b.b].lower_bound(j.b.a);
				jj--;
				int le=*jj;
				pre[j.b.b].insert(j.b.a);
				add(j.b.b,le,re,0);
				add(j.b.b,le,j.b.a,1);
				add(j.b.b,j.b.a,re,1);
			//}
		}
		else if(j.a.b==1){
			//remove 
			//continue;
			pre2[j.b.b][j.b.a]--;
			if(pre2[j.b.b][j.b.a]==0){
				pre[j.b.b].erase(j.b.a);
				int re=*(pre[j.b.b].lower_bound(j.b.a));
				auto jj=pre[j.b.b].lower_bound(j.b.a);
				jj--;
				int le=*jj;
				add(j.b.b,le,j.b.a,0);
				add(j.b.b,j.b.a,re,0);
				add(j.b.b,le,re,1);
				
			}
		}
		else{
			//cout<<j.b.a<<":"<<j.b.b<<endl;
			int ans2=query(0,0,nn-1,ss2[j.b.a]);
			if(ans2>1e8){
				ans2=-1;
			}
			ans[j.b.b]=ans2;
		}
	}
	for(int i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}
	/*for(int i=0;i<cur.size();i++){
		cur[i].b.a=ss2[cur[i].b.a];
	}*/





	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 228804 KB Output is correct
2 Correct 115 ms 228904 KB Output is correct
3 Correct 114 ms 228936 KB Output is correct
4 Correct 113 ms 228804 KB Output is correct
5 Correct 115 ms 228964 KB Output is correct
6 Correct 119 ms 229348 KB Output is correct
7 Correct 122 ms 229732 KB Output is correct
8 Correct 130 ms 229512 KB Output is correct
9 Correct 120 ms 229672 KB Output is correct
10 Correct 119 ms 229428 KB Output is correct
11 Correct 119 ms 229436 KB Output is correct
12 Correct 120 ms 229312 KB Output is correct
13 Correct 118 ms 229444 KB Output is correct
14 Correct 117 ms 229316 KB Output is correct
15 Correct 120 ms 229456 KB Output is correct
16 Correct 123 ms 229572 KB Output is correct
17 Correct 119 ms 229444 KB Output is correct
18 Correct 119 ms 229572 KB Output is correct
19 Correct 128 ms 229584 KB Output is correct
20 Correct 124 ms 229456 KB Output is correct
21 Incorrect 126 ms 229112 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 228804 KB Output is correct
2 Correct 115 ms 228904 KB Output is correct
3 Correct 114 ms 228936 KB Output is correct
4 Correct 113 ms 228804 KB Output is correct
5 Correct 115 ms 228964 KB Output is correct
6 Correct 119 ms 229348 KB Output is correct
7 Correct 122 ms 229732 KB Output is correct
8 Correct 130 ms 229512 KB Output is correct
9 Correct 120 ms 229672 KB Output is correct
10 Correct 119 ms 229428 KB Output is correct
11 Correct 119 ms 229436 KB Output is correct
12 Correct 120 ms 229312 KB Output is correct
13 Correct 118 ms 229444 KB Output is correct
14 Correct 117 ms 229316 KB Output is correct
15 Correct 120 ms 229456 KB Output is correct
16 Correct 123 ms 229572 KB Output is correct
17 Correct 119 ms 229444 KB Output is correct
18 Correct 119 ms 229572 KB Output is correct
19 Correct 128 ms 229584 KB Output is correct
20 Correct 124 ms 229456 KB Output is correct
21 Incorrect 126 ms 229112 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5115 ms 489580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5134 ms 672328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 228804 KB Output is correct
2 Correct 115 ms 228904 KB Output is correct
3 Correct 114 ms 228936 KB Output is correct
4 Correct 113 ms 228804 KB Output is correct
5 Correct 115 ms 228964 KB Output is correct
6 Correct 119 ms 229348 KB Output is correct
7 Correct 122 ms 229732 KB Output is correct
8 Correct 130 ms 229512 KB Output is correct
9 Correct 120 ms 229672 KB Output is correct
10 Correct 119 ms 229428 KB Output is correct
11 Correct 119 ms 229436 KB Output is correct
12 Correct 120 ms 229312 KB Output is correct
13 Correct 118 ms 229444 KB Output is correct
14 Correct 117 ms 229316 KB Output is correct
15 Correct 120 ms 229456 KB Output is correct
16 Correct 123 ms 229572 KB Output is correct
17 Correct 119 ms 229444 KB Output is correct
18 Correct 119 ms 229572 KB Output is correct
19 Correct 128 ms 229584 KB Output is correct
20 Correct 124 ms 229456 KB Output is correct
21 Incorrect 126 ms 229112 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 228804 KB Output is correct
2 Correct 115 ms 228904 KB Output is correct
3 Correct 114 ms 228936 KB Output is correct
4 Correct 113 ms 228804 KB Output is correct
5 Correct 115 ms 228964 KB Output is correct
6 Correct 119 ms 229348 KB Output is correct
7 Correct 122 ms 229732 KB Output is correct
8 Correct 130 ms 229512 KB Output is correct
9 Correct 120 ms 229672 KB Output is correct
10 Correct 119 ms 229428 KB Output is correct
11 Correct 119 ms 229436 KB Output is correct
12 Correct 120 ms 229312 KB Output is correct
13 Correct 118 ms 229444 KB Output is correct
14 Correct 117 ms 229316 KB Output is correct
15 Correct 120 ms 229456 KB Output is correct
16 Correct 123 ms 229572 KB Output is correct
17 Correct 119 ms 229444 KB Output is correct
18 Correct 119 ms 229572 KB Output is correct
19 Correct 128 ms 229584 KB Output is correct
20 Correct 124 ms 229456 KB Output is correct
21 Incorrect 126 ms 229112 KB Output isn't correct
22 Halted 0 ms 0 KB -