Submission #734144

#	Time	Username	Problem	Language	Result	Execution time	Memory
734144		Trunkty	Krave (COI14_krave)	C++14	100 / 100	1622 ms	82664 KiB

krave

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
 
int w,h,n;
set<vector<int>> vert[400020],hori[400020];
 
void addto(int node, int vl, int vr, int typ){
	if(typ==1){
		auto it = vert[node].lower_bound({vl,-1});
		if(it!=vert[node].end() and (*it)[0]<=vr){
			vr = max(vr,(*it)[1]);
			vl = min(vl,(*it)[0]);
			vert[node].erase(it);
		}
		it = vert[node].lower_bound({vl,-1});
		if(it!=vert[node].begin()){
			it--;
			if((*it)[1]>=vl){
				vr = max(vr,(*it)[1]);
				vl = min(vl,(*it)[0]);
				vert[node].erase(it);
			}
		}
		//cout << vl << " " << vr << " " << node << "\n";
		vert[node].insert({vl,vr});
	}
	else{
		auto it = hori[node].lower_bound({vl,-1});
		if(it!=hori[node].end() and (*it)[0]<=vr){
			vr = max(vr,(*it)[1]);
			vl = min(vl,(*it)[0]);
			hori[node].erase(it);
		}
		it = hori[node].lower_bound({vl,-1});
		if(it!=hori[node].begin()){
			it--;
			if((*it)[1]>=vl){
				vr = max(vr,(*it)[1]);
				vl = min(vl,(*it)[0]);
				hori[node].erase(it);
			}
		}
		hori[node].insert({vl,vr});
	}
}
 
void updatevert(int node, int l, int r, int pos, int vl, int vr){
	//cout << node << " " << l << " " << r << "\n";
	addto(node,vl,vr,1);
	if(l!=r){
		int mid = (l+r)/2;
		if(pos<=mid){
			updatevert(node*2,l,mid,pos,vl,vr);
		}
		else{
			updatevert(node*2+1,mid+1,r,pos,vl,vr);
		}
	}
}
 
void updatehori(int node, int l, int r, int pos, int vl, int vr){
	addto(node,vl,vr,2);
	if(l!=r){
		int mid = (l+r)/2;
		if(pos<=mid){
			updatehori(node*2,l,mid,pos,vl,vr);
		}
		else{
			updatehori(node*2+1,mid+1,r,pos,vl,vr);
		}
	}
}
 
bool isin(int node, int c, int typ){
	if(typ==1){
		auto it = vert[node].lower_bound({c,2000000000});
		if(it==vert[node].begin()){
			return false;
		}
		it--;
		if((*it)[1]>=c){
			return true;
		}
		else{
			return false;
		}
	}
	else{
		auto it = hori[node].lower_bound({c,2000000000});
		if(it==hori[node].begin()){
			return false;
		}
		it--;
		if((*it)[1]>=c){
			return true;
		}
		else{
			return false;
		}
	}
}
 
int queryvertlef(int node, int l, int r, int needl, int needr, int c){
	if(l>needr or r<needl){
		return 2e9;
	}
	else if(l>=needl and r<=needr){
		if(isin(node,c,1)){
			int mid = (l+r)/2;
			if(l==r){
				return l;
			}
			else if(isin(node*2+1,c,1)){
				return queryvertlef(node*2+1,mid+1,r,needl,needr,c);
			}
			else{
				return queryvertlef(node*2,l,mid,needl,needr,c);
			}
		}
		else{
			return 2e9;
		}
	}
	else{
		int mid = (l+r)/2;
		int b = queryvertlef(node*2+1,mid+1,r,needl,needr,c);
		if(b<2e9){
			return b;
		}
		else{
			return queryvertlef(node*2,l,mid,needl,needr,c);
		}
	}
}
 
int queryvertrit(int node, int l, int r, int needl, int needr, int c){
	if(l>needr or r<needl){
		return 2e9;
	}
	else if(l>=needl and r<=needr){
		if(isin(node,c,1)){
			int mid = (l+r)/2;
			if(l==r){
				return l;
			}
			else if(isin(node*2,c,1)){
				return queryvertrit(node*2,l,mid,needl,needr,c);
			}
			else{
				return queryvertrit(node*2+1,mid+1,r,needl,needr,c);
			}
		}
		else{
			return 2e9;
		}
	}
	else{
		int mid = (l+r)/2;
		int a = queryvertrit(node*2,l,mid,needl,needr,c);
		if(a<2e9){
			return a;
		}
		else{
			return queryvertrit(node*2+1,mid+1,r,needl,needr,c);
		}
	}
}
 
int queryhoridow(int node, int l, int r, int needl, int needr, int c){
	if(l>needr or r<needl){
		return 2e9;
	}
	else if(l>=needl and r<=needr){
		if(isin(node,c,2)){
			int mid = (l+r)/2;
			if(l==r){
				return l;
			}
			else if(isin(node*2+1,c,2)){
				return queryhoridow(node*2+1,mid+1,r,needl,needr,c);
			}
			else{
				return queryhoridow(node*2,l,mid,needl,needr,c);
			}
		}
		else{
			return 2e9;
		}
	}
	else{
		int mid = (l+r)/2;
		int b = queryhoridow(node*2+1,mid+1,r,needl,needr,c);
		if(b<2e9){
			return b;
		}
		else{
			return queryhoridow(node*2,l,mid,needl,needr,c);
		}
	}
}
 
int queryhoriup(int node, int l, int r, int needl, int needr, int c){
	if(l>needr or r<needl){
		return 2e9;
	}
	else if(l>=needl and r<=needr){
		if(isin(node,c,2)){
			int mid = (l+r)/2;
			if(l==r){
				return l;
			}
			else if(isin(node*2,c,2)){
				return queryhoriup(node*2,l,mid,needl,needr,c);
			}
			else{
				return queryhoriup(node*2+1,mid+1,r,needl,needr,c);
			}
		}
		else{
			return 2e9;
		}
	}
	else{
		int mid = (l+r)/2;
		int a = queryhoriup(node*2,l,mid,needl,needr,c);
		if(a<2e9){
			return a;
		}
		else{
			return queryhoriup(node*2+1,mid+1,r,needl,needr,c);
		}
	}
}
 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> w >> h >> n;
	updatevert(1,0,w,0,0,h);
	updatevert(1,0,w,w,0,h);
	updatehori(1,0,h,0,0,w);
	updatehori(1,0,h,h,0,w);
	/*
	cout << queryvertlef(1,0,w,0,w,0) << "\n";
	cout << queryvertlef(1,0,w,0,w,1) << "\n";
	cout << queryvertlef(1,0,w,0,w-1,h) << "\n";
	cout << queryhoridow(1,0,h,0,h,0) << "\n";
	cout << queryhoridow(1,0,h,0,h,1) << "\n";
	cout << queryhoridow(1,0,h,0,h-1,w) << "\n";
	*/
	for(int i=1;i<=n;i++){
		int a,b,c;
		cin >> a >> b >> c;
		int up=queryhoriup(1,0,h,b,h,a);
		int down=queryhoridow(1,0,h,0,b,a);
		int lef=queryvertlef(1,0,w,0,a,b);
		int rit=queryvertrit(1,0,w,a,w,b);
		if(c==1){
			cout << min((up-b)*(rit-lef),(b-down)*(rit-lef)) << " " << max((up-b)*(rit-lef),(b-down)*(rit-lef)) << "\n";
			updatehori(1,0,h,b,lef,rit);
		}
		else{
			cout << min((up-down)*(rit-a),(up-down)*(a-lef)) << " " << max((up-down)*(rit-a),(up-down)*(a-lef)) << "\n";
			updatevert(1,0,w,a,down,up);
		}
	}
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12