글 읽기 - 세그먼트 트리로 푸는데 시간을 어떻게 더 줄일 수 있을까요?

hwy16016 3년 전 0

계속 시간초과가 납니다

37번째 줄에서 O(N^2logN)이기 때문에 시간초과가 나는 것 같은데

줄일 수 있는 방법이 떠오르지 않네요ㅠㅠ

세그먼트 트리에서 i가 정해져 있을 때 i번째 노드부터 j번째 노드까지의 합이 K인 j를 구하는 효율적인 방법이 있을까요?

#include<cstdio>
#include<vector>
#include<cmath>
#define mid(s, e) ((s+e)/2)
using namespace std;
typedef vector<int> vi;

int init(vi& num, vi& st, int tidx, int s, int e);
void update(vi& st, int tidx, int s, int e, int nidx, int diff);
int findsum(vi& st, int tidx, int s, int e, int fl, int fr);

int main()
{
	int N, K, M;
	scanf("%d %d %d", &N, &K, &M);
	vi num(N, 1);
	int h=0;
	for(int i=1;i<N;i*=2, h++);
	vi st(pow(2, h+1), 0);
	init(num, st, 1, 0, N-1);
	M--;
	int cnt=0, cur=-1;
	while(num[M]!=0){
		cnt++;
		int tsum=st[1], curk=K;
		while(tsum<curk) curk%=tsum;//substract st[0]
		if(curk==0) curk=tsum;
		cur=(cur+1)%N;
		tsum=findsum(st, 1, 0, N-1, cur, N-1);
		if(tsum<curk){
			curk-=tsum;//substract remaining part of st to calc with s=0
			cur=0;
		}
		
		for(int i=curk-1;i<N;i++){
			if(num[cur+i]==0) continue;
			if(curk==findsum(st, 1, 0, N-1, cur, cur+i)){
				cur+=i;
				num[cur]=0;
				update(st, 1, 0, N-1, cur, -1);
				break;
			}
		}
	}
	printf("%d", cnt);
	return 0;
}

int init(vi& num, vi& st, int tidx, int s, int e){
	if(s==e) return st[tidx]=num[s];
	return st[tidx]=init(num, st, tidx*2, s, mid(s, e))+init(num, st, tidx*2+1, mid(s, e)+1, e);
}

void update(vi& st, int tidx, int s, int e, int nidx, int diff){
	if(nidx<s || nidx>e) return;
	st[tidx]+=diff;
	if(s!=e){
		update(st, tidx*2, s, mid(s, e), nidx, diff);
		update(st, tidx*2+1, mid(s, e)+1, e, nidx, diff);
	}
}

int findsum(vi& st, int tidx, int s, int e, int fl, int fr){
	if(s>fr || e<fl) return 0;
	if(fl<=s && fr>=e) return st[tidx];
	return findsum(st, tidx*2, s, mid(s, e), fl, fr)+findsum(st, tidx*2+1, mid(s, e)+1, e, fl, fr);
}

hwy16016 3년 전 0

결국 아래 질문에 나와있는것 처럼 상대적인 위치로 풀었는데

세그먼트 트리를 이용해서 시간내에 풀 수 있는 방법은 없는걸까요?

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

문제

문제

출처

ICPC

세그먼트 트리로 푸는데 시간을 어떻게 더 줄일 수 있을까요?

hwy16016 3년 전 0

hwy16016 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말