oj.uz

답안 #734144

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734144 2023-05-01T22:47:33 Z Trunkty Krave (COI14_krave) C++14
100 / 100
 1622 ms 82664 KB 
#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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 37964 KB Output is correct
2 Correct 18 ms 37832 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 38660 KB Output is correct
2 Correct 26 ms 38604 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 645 ms 69136 KB Output is correct
2 Correct 384 ms 53156 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 651 ms 69508 KB Output is correct
2 Correct 435 ms 55244 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 675 ms 69488 KB Output is correct
2 Correct 565 ms 57592 KB Output is correct

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 622 ms 59284 KB Output is correct
2 Correct 372 ms 59712 KB Output is correct

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1622 ms 82564 KB Output is correct
2 Correct 419 ms 62816 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1565 ms 79932 KB Output is correct
2 Correct 320 ms 49796 KB Output is correct
3 Correct 471 ms 59440 KB Output is correct
4 Correct 464 ms 64388 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1615 ms 82664 KB Output is correct
2 Correct 329 ms 51248 KB Output is correct
3 Correct 491 ms 59836 KB Output is correct
4 Correct 479 ms 66072 KB Output is correct

Subtask #10
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1540 ms 82584 KB Output is correct
2 Correct 300 ms 50952 KB Output is correct
3 Correct 523 ms 59868 KB Output is correct
4 Correct 514 ms 67524 KB Output is correct