글 읽기 - 시간초과의 원인을 도저히 모르겠습니다.

vl0612 4년 전 0

이진탐색 쪽에서 무한루프 도는 건가 검토도 해보고 인터넷 반례도 노가다로 다 넣어봤습니다.

원인을 도저히 모르겠습니다ㅠㅠ

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,Q,m;
struct ipt{ int val,ord,idx; } arr[100001];
map<int,int> cto;

int root[100001];
struct node{ int l,r,req; } tree[1<<22]; int tn=0;

void make(int a,int s,int e){ //s부터 e까지 만듬
	if(s==e) tree[a].l=0, tree[a].r=0, tree[a].req=0;
	else {
		tree[a].l = ++tn; tree[a].r = ++tn;
		make(tree[a].l,s,(s+e)/2); make(tree[a].r,(s+e)/2+1,e);
	}
}
void add(int bef, int a, int s, int e, int d, int f){//이전 tree/현재노드/ s부터 e탐색 중 d에 f넣기 
	if(s==e) tree[a].l = 0, tree[a].r = 0, tree[a].req = f;
	else {
		if(d<=(s+e)/2){ //d가 좌측에 있는 경우 
			tree[a].l = ++tn; tree[a].r = tree[bef].r;
			add(tree[bef].l,tree[a].l,s,(s+e)/2,d,f);
		} else { //우측에 있는 경우 
			tree[a].l = tree[bef].l; tree[a].r = ++tn;
			add(tree[bef].r,tree[a].r,(s+e)/2+1,e,d,f); 
		}
		tree[a].req = tree[tree[a].l].req + tree[tree[a].r].req;
	}
}
int query(int a, int s, int e, int d, int f){//d부터 f까지 
	if(s==e) return tree[a].req;
	else {
		int mid = (s+e)/2;
		if(f<=mid) return query(tree[a].l,s,mid,d,f);
		else if(mid+1<=d) return query(tree[a].r,mid+1,e,d,f);
		else return query(tree[a].l,s,mid,d,mid) + query(tree[a].r,mid+1,e,mid+1,f);
	}
}
int main(){//멍멍 
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>arr[i].val, arr[i].idx=i;
	//전처리 
	sort(arr+1,arr+n+1,[&](ipt a,ipt b){return a.val<b.val;});
	for(int i=1;i<=n;i++)
		arr[i].ord=i, cto[arr[i].ord]=arr[i].val;
 	//pst 구축 
	for(int i=0;i<(1<<22);i++) tree[i] = (node) {0,0,0};
	root[0] = ++tn;
	make(root[0],1,n);
	for(int i=1;i<=n;i++) root[i] = ++tn, add(root[i-1],root[i],1,n,arr[i].idx,1);
	//쿼리 처리
	int a,b,k,l,r,now,ans;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>k;
		l=1;r=n;
		ans=0;
		while(l<=r){
			now = query(root[(l+r)/2],1,n,a,b);
			if(now<k) l = (l+r)/2+1;
			else {
				if(now==k){
					if(ans==0) ans=(l+r)/2;
					else ans=min(ans,(l+r)/2);
				}
				r = (l+r)/2-1;
			}
		}
		cout<<cto[ans]<<'\n';
	}
}

djm03178 4년 전 1

현재의 query 함수는 세그먼트 트리의 기능을 전혀 활용하지 못하고 있습니다. 쿼리 구간 전체가 노드가 담당하는 구간 전체에 걸쳐있으면 바로 반환을 해야 하는데, 현재 query 함수는 무조건 s==e인 곳까지 다 들어가기 때문에 결국 구간의 길이에 비례하는만큼 탐색하게 됩니다.

vl0612 4년 전 0

오오오 긴코드 바주셔서 감사합니다 ㅎㅎ

s==d && e==f 로 고치니까 맞았습니당!!!

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

문제

문제

출처

ICPC

시간초과의 원인을 도저히 모르겠습니다.

vl0612 4년 전 0

djm03178 4년 전 1

vl0612 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말