[8-J] 시간초과 문의드립니다.

작성한 질문수 8

1

안녕하세요 ㅎㅎ

문제 범위를 볼까요?

영화의 수 n과 보려고 하는 영화의 수 m이 주어진다. (1 ≤ n, m ≤ 100,000)

지금 보시면 m은 최대 10만이 될 수 있습니다. 여기서 펜윅트리는 인덱스가 1부터 시작하죠.

        int mi=gap;
        for(int i=0;i<m;i++){
            cin>>here;
            cout << cal(mp[here])-1<<" ";
            update(mp[here], -1);
            update(--mi,1);

이코드를 보시면 mi를 m만큼 --하는 것을 볼 수 있습니다. 만약 m이 10만이라면 mi는 0이라는 인덱스를 가질 수도 있게 되어 -> 펜윅트리가 제대로 업데이트가 안되서 -> 시간초과가 뜨는 것 같습니다.

void update(int i, int val){
    while (i<200004){
        tr[i]+=val;
        i+=i&-i;
    }
}

update함수를 보면 다음과 같은데요. i가 0이라면 계속해서 실행이 될 것 같습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.