글 읽기 - 모스 알고리즘 런타임에러

nuclear852 3년 전 0

자꾸 런타임에러가 뜨는데 왜 뜨는지 솔직히 모르겠습니더..

코드 논리가 문제여서 뜨는 건지 아니면 코딩이 잘못됐는지 알려주시면 감사하겠습니더..

#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;
int N, M, C;
int cnt[101010];
int arr[101010];
int ans[101010];

int bket[404040];
int Sbket[101010];
int now;
int sq;

struct query {
    int left, right, index;
} Q[10001];

bool cmp(const query& a, const query& b) {
    int aSR = a.right / sq;
    int bSR = b.right / sq;
    
    return aSR == bSR ? a.left < b.left : aSR < bSR;
}

void f(int index, bool add) {
    int tmp = (int)cnt[arr[index]] / sq;
    if(Sbket[tmp] > 0) {
        Sbket[tmp]--;
        bket[cnt[arr[index]]]--;
    }
    if(add) {
        cnt[arr[index]]++;
    }
    else {
        cnt[arr[index]]--;
    }
    bket[cnt[arr[index]]]++;
    tmp = (int)cnt[arr[index]]/ sq;
    Sbket[ tmp]++;
}

int find_ans() {
    for(int j=sq; j>=0; j--) {
        if(Sbket[j] > 0) {
            for(int k=sq-1; k>=0; k--) {
                if( bket[j*sq+k] > 0 ) {
                    return j*sq+k;
                }
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d", &N);
    sq = (int)sqrt(N);
    for(int i=1; i<=N; i++) {
        scanf("%d", &arr[i]);
    }
    scanf("%d", &M);
    for(int i=1; i<=M; i++) {
        scanf("%d%d", &Q[i].left, &Q[i].right);
        Q[i].index = i;
    }
    sort(Q+1, Q+M+1, cmp);
    int lo = 1, hi = 0;
    for(int i=1; i<=M; i++) {
        while(Q[i].left < lo) {
            f(--lo, true);
        }
        while(Q[i].left > lo) {
            f(lo++, false);
        }
        while(Q[i].right > hi) {
            f(++hi, true);
        }
        while(Q[i].right < hi) {
            f(hi--, false);
        }

        // for(int i=0; i<=N; i++) {
        //     printf("%d ", cnt[i]);
        // }
        // printf("\n");
        // for(int i=0; i<=N; i++) {
        //     printf("%d ", bket[i]);
        // }
        // printf("\n");
        ans[Q[i].index] = find_ans();
    }

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

djm03178 3년 전 1

쿼리가 최대 10만 개인데 Q 배열의 크기는 10001입니다.

nuclear852 3년 전 0

와.. 예리하시네요 bb 감사합니다 ㅋㅋㅋㅋㅋㅋㅋ

근데 50퍼에서 틀렸다네요... 함 고쳐보겠습니다

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

문제

문제

출처

ICPC

모스 알고리즘 런타임에러

nuclear852 3년 전 0

djm03178 3년 전 1

nuclear852 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말