글 읽기 - 테케는 맞는데,, 런타임 에러..

andrealgorithm 4년 전 0

ㄴ런타임 에러가 어디 부분에서 났는지 모르곘습니다..

단순히 배열 크기 문제 인덱스 문제는 아닌것 같은데... 고수님들 도와주세요

#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;
int n,m;
int collections[100001]={0};

int make_tree(vector<int> &tree, vector<int> &root_check, int index ,int start ,int end){
    if(start == end) return tree[index] = root_check[start];

    int mid = (start +end) /2;

    return tree[index] = make_tree(tree,root_check, index*2, start ,mid) + make_tree(tree,root_check,index*2+1, mid+1,end);
}

int getSum(vector<int> &tree, int index, int start ,int end, int left ,int right){
    if(start >right || end < left) return 0;

    if(left <= start && end <= right) return tree[index];

    int mid = (start + end)/2;

    return getSum(tree, index*2 ,start ,mid, left ,right) +getSum(tree ,index*2+1, mid+1, end, left ,right);
}

void update(vector<int> &tree, int index ,int start ,int end, int change_index ,int diff){
    if(change_index <start || change_index >end) return;

    tree[index] += diff;

    if(start == end) return ;

    int mid = (start + end)/2;

    update(tree,index*2, start, mid ,change_index, diff);
    update(tree,index*2+1, mid+1, end, change_index, diff);
}

int main(){
    int T;
    scanf("%d",&T);

    for(int test_case =1; test_case <=T; test_case++){
        scanf("%d %d",&n,&m);

        vector<int> collections(n+1);
        vector<int> root_check(n*2+2,0); //기존 arr 개념, 0,1 로 구성 
        vector<int> tree(n*4+4);

        for(int i =1; i<=n; i++){
            root_check[i+m]=1;    //m+i 번째부터 0,1 값을 통해 자리수 카운팅 
            collections[i] = i+m;  
        }

        make_tree(tree,root_check,1,1,n+m);

        int temp;
        int dex =m;
        for(int i =0; i<m; i++){
            scanf("%d",&temp);
            int ans = getSum(tree, 1, 1, n+m, 1, collections[temp])-1;

            update(tree,1 ,1, n+m, collections[temp],-1);
            update(tree,1 ,1, n+m, dex,1);

            collections[temp] = dex;
            dex--;
            printf("%d ",ans);
        }
    }

    return 0;
}

yehyun 4년 전 0

저는 코드를 살펴보지 않았지만 아래와 같은 입력에서 segmentation fault가 발생합니다.

비교적 작은 입력이니 흐름을 따라가보시면 될 듯 합니다.

input
1
2 4
2 1 2 2
    
answer
1 1 1 0

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

문제

문제

출처

ICPC

테케는 맞는데,, 런타임 에러..

andrealgorithm 4년 전 0

yehyun 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말