글 읽기 - 5480번 전함 질문입니다

wwiiiii 9년 전 0

음...segment tree는 처음 짜봐서 소스가 좀 많이 길어졌는데 ㅠㅠ 죄송합니다...
그런데 제가 만든 테스트 케이스에서는 전부 무리 없이 실행되는데 왜 채점하면 바로 첫번째 데이터에서 시간초과가 나는지 모르겠어요.
/**
x성분 구간트리(n이상인 최초의 2의 제곱수 BIN에 대해 크기가 2BIN인 배열)
y성분 구간트리(n이상인 최초의 2의 제곱수 BIN에 대해 크기가 2BIN인 배열)
전함 index가 최초로 파괴 되게한 광선의 ID를 저장하는 배열
index번째 광선이 파괴한 전함 중 최대의 무게를 저장하는 배열
**/

#include <cstdio>
#include <set>
#include <algorithm>
#include <vector>
#define INF 2012345678
using namespace std;
typedef struct coord{ int x; int y; } coord;
typedef struct edge{ coord from; coord to; int weight; } edge;
typedef struct SEG{
	vector<int> intervals;///그 점을 포함하는 구간의 번호들
}SEG;
int n, k, l;
vector<edge> gunships;
int BIN;
int ShipDestroyedBy[1200000];///전함 index가 최초로 파괴 되게한 광선의 ID를 저장하는 배열
int DestroyedHeavy[200010];///index번째 광선이 파괴한 전함 중 최대의 무게를 저장하는 배열
SEG segx[1200000];///구간들의 번호
SEG segy[1200000];///구간들의 번호
set<int> px, py;///임시
vector<int> ppx, ppy;

int xpos(int target)///ppx에서 target의 위치를 반환
{
	int l, r, m;
	l = 0, r = ppx.size() - 1;
	while (l<r){
		m = (l + r) / 2;
		if (ppx[m] < target) l = m + 1;
		else if (ppx[m] > target) r = m - 1;
		else break;
	}
	while (ppx[m] < target) ++m;
	while (ppx[m] > target) --m;
	return m;

}

int ypos(int target)///ppx에서 target의 위치를 반환
{
	int l, r, m;
	l = 0, r = ppy.size() - 1;
	while (l<r){
		m = (l + r) / 2;
		if (ppy[m] < target) l = m + 1;
		else if (ppy[m] > target) r = m - 1;
		else break;
	}
	while (ppy[m] < target) ++m;
	while (ppy[m] > target) --m;
	return m;
}

void Init(){
	n = k = l;
	gunships.clear(); px.clear(); py.clear();
	ppx.clear(); ppy.clear();
}

void task()
{
	int a, b, nx, ny, BINx, BINy, t1, t2;
	edge ed; int w;
	SEG filling; filling.intervals.clear();
	Init();
	scanf("%d%d%d", &n, &k, &l);
	fill(&DestroyedHeavy[0], &DestroyedHeavy[l+1], 0);
	fill(&ShipDestroyedBy[0], &ShipDestroyedBy[k], 0);
	for (int i = 0; i<k; i++)
	{
		scanf("%d %d %d %d %d", &ed.from.x, &ed.from.y, &ed.to.x, &ed.to.y, &ed.weight);
		///swap
		t1 = min(ed.from.x, ed.to.x);
		t2 = max(ed.from.x, ed.to.x);
		ed.from.x = t1; ed.to.x = t2;
		t1 = min(ed.from.y, ed.to.y);
		t2 = max(ed.from.y, ed.to.y);
		ed.from.y = t1; ed.to.y = t2;

		gunships.push_back(ed);
		px.insert(ed.from.x); px.insert(ed.to.x);
		py.insert(ed.from.y); py.insert(ed.to.y);
	}
	///leaf nodes exist in range segx[BIN] ~ segx[BIN+n-1]
	for (set<int>::iterator it = px.begin(); it != px.end(); ++it) ppx.push_back(*it);
	for (set<int>::iterator it = py.begin(); it != py.end(); ++it) ppy.push_back(*it);
	nx = ppx.size(); ny = ppy.size();
	BINx = BINy = 1;
	while (BINx < 2 * (nx + 3)) BINx *= 2;
	while (BINy < 2 * (ny + 3)) BINy *= 2;
	if (2 * BINx + 10 < 600000)fill(&segx[0], &segx[2 * BINx + 10], filling); else fill(&segx[0], &segx[600000], filling);
	if (2 * BINy + 10 < 600000)fill(&segy[0], &segy[2 * BINy + 10], filling); else fill(&segy[0], &segy[600000], filling);

	///update
	for (int i = 0; i < gunships.size(); ++i)
	{
		int lindex, rindex;///seg에서의 인덱스
		lindex = BINx + 2 * xpos(gunships[i].from.x) + 1;
		rindex = BINx + 2 * xpos(gunships[i].to.x) + 1;
		while (lindex <= rindex)
		{
			//printf("seg : [%d,%d] ,lindex [%d->%d] rindex [%d->%d]\n", gunships[i].from.x, gunships[i].to.x, lindex, segx[lindex].to, rindex, segx[rindex].to);
			if (lindex % 2 == 0) lindex /= 2;///왼쪽자식
			else { segx[lindex].intervals.push_back(i); lindex /= 2; lindex++; }///오른쪽자식
			if (rindex % 2 == 1) rindex /= 2;///오른쪽자식
			else { segx[rindex].intervals.push_back(i); rindex /= 2; rindex--; }///오른쪽자식
		}

		lindex = BINy + 2 * ypos(gunships[i].from.y) + 1;
		rindex = BINy + 2 * ypos(gunships[i].to.y) + 1;

		while (lindex <= rindex)
		{
			if (lindex % 2 == 0) lindex /= 2;///왼쪽자식
			else { segy[lindex].intervals.push_back(i); lindex /= 2; lindex++; }///오른쪽자식
			if (rindex % 2 == 1) rindex /= 2;///오른쪽자식
			else { segy[rindex].intervals.push_back(i); rindex /= 2; rindex--; }///오른쪽자식
		}
	}


	for (int cnt = 1; cnt <= l; ++cnt)///query
	{
		scanf("%d %d", &a, &b);
		if (b == 0)///destroy (1,a) ~ (n,a) ==> find intervals that include y coord a, segy
		{
			if (a < ppy[0] || a> ppy[ny-1]) continue;
			int chase;
			int temp = *lower_bound(ppy.begin(), ppy.end(), a);
			chase = BINy + 2 * ypos(temp) + 1;
			if (temp != a) chase--;
			//printf("query : destroy %d, in y//Seg start in %d\n", a, chase);
			while (chase > 0)///report the ID of intervals that include ~
			{
				for (int i = 0; i < segy[chase].intervals.size(); i++) {
					if (ShipDestroyedBy[segy[chase].intervals[i]] == 0) ShipDestroyedBy[segy[chase].intervals[i]] = cnt;
				//	printf("Laser[%d] :: Ship[%d] destroyed\n", cnt, segy[chase].intervals[i]);
				}
				chase /= 2;
			}
		}
		else
		{
			if (a < ppx[0] || a> ppx[nx-1]) continue;
			int chase;
			int temp = *lower_bound(ppx.begin(), ppx.end(), a);
			chase = BINx + 2 * xpos(temp) + 1;
			if (temp != a) chase--;
			//printf("query : destroy %d, in x//Seg start in %d\n", a, chase);
			while (chase > 0)///report the ID of intervals that include ~
			{
				for (int i = 0; i < segx[chase].intervals.size(); i++){
					if (ShipDestroyedBy[segx[chase].intervals[i]] == 0) ShipDestroyedBy[segx[chase].intervals[i]] = cnt;
					//printf("Laser[%d] :: Ship[%d] destroyed\n", cnt, segx[chase].intervals[i]);
				}
				chase /= 2;
			}
		}
	}

	for (int i = 0; i<gunships.size(); ++i)
	{
		int nowweight = gunships[i].weight;
		int LaserID = ShipDestroyedBy[i];
		DestroyedHeavy[LaserID] = max(nowweight, DestroyedHeavy[LaserID]);
	}

	for (int i = 1; i <= l; ++i)
	{
		printf("%d\n", DestroyedHeavy[i]);
	}
	return;
}


int main()
{
	int T; scanf("%d", &T);
	while (T--) task();
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

5480번 전함 질문입니다

wwiiiii 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
