글 읽기 - 화성지도 도움이 절실합니다 ㅠㅠㅠ

mic1021 8년 전 0

이 문제 할 때 plane sweeping 쓰는 건 알겠습니다. x축을 따라서 지도가 있는 넓이를 더해주는 식으로 구현하려고 했더니 문제가 생겼습니다.특정x값에서의 전체 y범위 중 특정y범위는 지도가 겹치는 부분일테고 어떤 y범위는 아예 지도가 없는 부분일 테고 어떤 y범위는 지도가 하나있는 부분일텐데 이런 정보들을 segment tree내에 어떻게 저장해야 되는지가 고민입니다.

#include <cstdio>
#include <vector>
using namespace std;
#define MAX 30001
#define max(a,b)((a)>(b)?(a):(b))
#define min(a,b)((a)>(b)?(b):(a))
int seg_tree[4*MAX];
int lazy[4*MAX];
vector <pair<int,int> > start[MAX];
vector <pair<int,int> > last[MAX];
void upd(int p,int s,int e,int l,int r,int val);
int sum(int p,int s,int e);
int cnt;
int main () {
	int N;
	scanf("%d",&N);
	int m=-1;
	int n=987654321;
	while(N--){
		int x1,y1,x2,y2;
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		start[x1].push_back(make_pair(y1,y2));
		last[x2].push_back(make_pair(y1,y2));
		n=min(n,x1);
		m=max(m,x2);
	}
	int ans=0;
	int prev=n;
	int now=n;
	for(int i=n;i<=m;i++){
		if(!start[i].empty() || !last[i].empty()){
			ans+=(now-prev)*seg_tree[1];
			for(int j=0;j<(int)start[i].size();j++){
				int down=start[i][j].first;
				int up=start[i][j].second-1;
				upd(1,1,30000,down+1,up+1,1);
			}
			for(int j=0;j<(int)last[i].size();j++){
				int down=last[i][j].first;
				int up=last[i][j].second-1;
				upd(1,1,30000,down+1,up+1,-1);
			}
			prev=now;
		}
		now++;
	}
	printf("%d\n",ans);
	return 0;
}
void upd(int p,int s,int e,int l,int r,int val){
	if(r<s || e<l) return ;
	cnt++;
	if(lazy[p]!=0){
		if(s!=e){
			lazy[2*p]+=lazy[p];
			lazy[2*p+1]+=lazy[p];
		}
		seg_tree[p]+=lazy[p];
		lazy[p]=0;
	}
	if(l<=s && e<=r && seg_tree[p]!=-1) {
		lazy[p]+=val;
		if(val ==1 && seg_tree[p]==0) seg_tree[1]+=(e-s+1);
		else if(val==-1 && seg_tree[p]==1) seg_tree[1]-=(e-s+1);
	}
	else{
		upd(2*p,s,(s+e)/2,l,r,val);
		upd(2*p+1,(s+e)/2+1,e,l,r,val);
		if((seg_tree[2*p]+lazy[2*p]) == (seg_tree[2*p+1]+lazy[2*p+1]) && seg_tree[2*p]!=-1)
			seg_tree[p]=seg_tree[2*p]+lazy[2*p];
		else if(p!=1) seg_tree[p]=-1;
	}
}

ntopia 8년 전 0

지금 이 소스 안에서 설명을 드리자면

세그먼트 트리에다가 왼쪽 변이 등장하면 +1, 오른쪽 변이 등장하면 -1 을 하고 있는 것 같은데,

우리는 합집합의 넓이를 구해야 하잖아요?

생각해보면 세그먼트 트리에서 값이 0보다 큰 부분이면 정사각형이 하나 이상은 덮인 곳이겠죠?

이 부분들의 개수를 세서 (now-prev) 와 곱하면 될 것 같습니다.

세그먼트 트리 업데이트 할 때 0보다 큰 부분의 개수를 세는 코드를 추가해야 겠네요...

mic1021 8년 전 0

만약 기존에 1~3 과 7~8이 채워진 상황에서 1~9가 채워지면 1~3과 7~8은 두번 겹치고 4~6과 9는 한번만 채워진 상황일텐데요

이 때 1~9구간에 해당하는 seg_tree배열값에 +1 해주는 게 맞나요? 아니면 1~9 아래로 내려가서 1~3이랑 4랑 5~6이랑 7~8이랑 9에 각각 +1해주는게 맞나요?

mic1021 8년 전 0

예를 들어서 1~9구간에서 -1 해야 되는데 1~4 와 7~9는 두번 겹친 상황이고 5~6은 하나만 있는 상황 일 때는 seg_tree배열의 1~9구간에 해당하는 값에서 -1해주면 안되잖아요? 그래서 아래로 내려가라는 표시로 seg_tree배열의 1~9구간에 해당하는 값을 -1로 설정했는데요.. 이런식으로 계속 내려가게 되면 재귀호출의 수가 증가해버려서 시간초과가 뜨게 됩니다...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

화성지도 도움이 절실합니다 ㅠㅠㅠ

mic1021 8년 전 0

ntopia 8년 전 0

mic1021 8년 전 0

mic1021 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말