글 읽기 - 런타임 에러(도움 부탁드립니다! ㅠㅠ)

83tachyon 3년 전 0

세그먼트 트리 활용하여 풀었습니다. 하단 코드에 코멘트 넣었습니다.

세그트리의 사이즈 절반이 되는 지점부터 1을 넣어 dvd의 위치를 표시하였고,

그 dvd가 맨 위로 올라갈 때마다 처음 자리에 0으로 바꿔주고 새 위치에 1을 넣었습니다.

그리고 이번에 보려고 하는 dvd의 위치에서부터 맨 뒤까지를 구간으로 잡아 sum함수를 돌리고

마지막에 자기자신을 빼서(-1) 답을 구하는 방식입니다.

질문검색 게시판에서 테케 사이트 찾게되어 테케 파일을 돌려보았습니다.

그냥 통째로 돌리면 몇개 돌다가 중간에 bus error / segmentation fault 에러가 발생하고,

혹시 그 테케가 잘못된 건가 싶어서 따로 빼서 돌려보면 또 잘 돌아갑니다.

그 이후의 테케들을 모두 모아서 한꺼번에 돌리면 또 몇개 가다가 같은 에러가 발생합니다.

제 혼자만의 추측은 테케에서 다음 테케로 가는 과정에서 뭔가 리셋이 제대로 안되고 있다는 느낌인데,

확실하지 않구요. 어떤게 문제인지 가늠이 안됩니다.

고수분들의 도움이 절실합니다. ㅠㅠ

#include <fstream>
#include <iostream>
#define endl '\n'
using namespace std;
const int dvd=1e5+1;

// 세그트리를 구성할때 n+m개를 넘는 2^(자연수) 사이즈를 먼저 찾고,
// 그 크기에 한번 더 2배를 하였습니다.
// 그렇게 함으로써, (나머지 부분은 모두 0으로 채워져있으므로) 균형포화이진트리(?)
// 를 만들 수 있고, 세그트리를 완성할 수 있다고 생각하였습니다.

// 넉넉하게 dvd의 8배를 주었습니다.
int t,n,m,pos[dvd],seg[dvd*8],num,sz=1;
// pos 배열은 해당 dvd의 세그먼트 트리상에서의 위치(인덱스)를 나타냅니다.
// 16개 짜리 크기의 세그트리의 경우, 8번부터 dvd를 배치하고 8번이 pos배열에 들어가는
// 숫자가 됩니다.

// 일반적인 세그트리의 함수들입니다. (sum, update, construct)
int sum(int s,int e,int idx,int a,int b){
    if(b<s||a>e)return 0;
    if(a<=s&&e<=b)return seg[idx];
    int mid=(s+e)/2;
    return sum(s,mid,idx*2,a,b)+sum(mid+1,e,idx*2+1,a,b);
}
void update(int idx,int i){
    
    // 기존의 위치를 0으로 바꾸고 새 위치에 1을 넣어주기 때문에
    // 세그트리를 타고 올라가는 update가 2번 필요합니다.
    seg[idx]=0;
    while(idx>0){
        idx/=2;
        seg[idx]=seg[idx*2]+seg[idx*2+1];
    }
    
    // 새 위치(idx)는 처음위치로 배정된 dvd들 다음의 인덱스로 이동합니다
    // 여기서의 i는 main함수에서의 0~m범위입니다.
    idx=sz/2+n+i;
    pos[num]=idx;
    seg[idx]=1;
    while(idx>0){
        idx/=2;
        seg[idx]=seg[idx*2]+seg[idx*2+1];
    }
}
void construct(){
    for(int i=sz/2-1;i>=1;--i){
        seg[i]=seg[i*2]+seg[i*2+1];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    //ifstream fin("ctest1.in");
    //ofstream fout("cres2.out");

    cin>>t;
    //fin>>t;
    while(t--){
        cin>>n>>m;
        //fin>>n>>m;
        
        // 여기서 세그트리의 크기를 정해줍니다. n+m을 아우르는 크기를 구한 후
        // 다시 2배를 해줍니다.
        while(sz<(n+m))sz*=2;
        sz*=2;
        
        // 이번 회차(테케)에 사용하는 범위까지 0으로 리셋해줍니다
        fill(seg,seg+sz,0);
        for(int i=n;i>=1;--i){
            int ps=sz/2+n-i;
            pos[i]=ps;
            seg[ps]=1;
        }
        construct();
        for(int i=0;i<m;++i){
            cin>>num;
            //fin>>num;
            cout<<sum(1,sz/2,1,pos[num]-sz/2+1,sz/2)-1<<' ';
            //fout<<sum(1,sz/2,1,pos[num]-sz/2+1,sz/2)-1<<' ';
            update(pos[num],i);
        }
        cout<<endl;
        //fout<<endl;
    }
    return 0;
}

djm03178 3년 전 1

sz가 초기화되지 않아서, 이미 충분한 크기인데도 강제로 2배가 추가될 수 있어 보입니다.

83tachyon 3년 전 0

djm03178 님 안녕하세요

그간 공부하면서 많은 문제들의 질문 게시판에서 계속 은혜를 입고 있었습니다.

너무나 빠른 답변 감사드립니다. sz초기화 찾아주셔서 감사합니다. 덕분에 AC 받았습니다. ㅠㅠ

한가지 더 여쭤보고 싶은 점이 있습니다

예를 들어, n=15일 때, 균형포화이진트리(?)형태의 세그트리 구성을 위해 15보다 살짝 큰 사이즈 16을 쓴다면

세그트리 구성이 불가능함이 자명합니다. 그래서 저는 while루프를 나오고나서 2배를 한번 더 해주었습니다.

이러한 방식의 세그트리 구성이 괜찮은건가요?

균형포화이진트리를 구성하면 sum함수 호출등의 쿼리를 수행할때 항상 전범위로 잡아주면 되기때문이라고 생각하고 있습니다.

djm03178 3년 전 1

그 방법을 실제로 비재귀 세그트리에서 사용합니다. 유효하지 않은 인덱스에 대한 처리만 잘 해주신다면 문제 없습니다.

83tachyon 3년 전 0

비재귀 세그트리가 무엇인지 따로 더 공부해야 하겠군요.

말씀 감사드립니다!

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

문제

문제

출처

ICPC

런타임 에러(도움 부탁드립니다! ㅠㅠ)

83tachyon 3년 전 0

djm03178 3년 전 1

83tachyon 3년 전 0

djm03178 3년 전 1

83tachyon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말