글 읽기 - 왜 시간초과가 나오는지 궁금합니다

marin663 2년 전 0

이분탐색 누적합 모두 적용해서 푼 풀이인데 계속 시간초과 나와서 실패했네요.. 이유좀 알려주세요

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(void){
    int H,Q,R;
    float cnt[100002]={0,};
    float ans;
    long long arrh[100001];
    int temp1,temp2,hole,new;
    arrh[0]=0;
    scanf("%d",&H);
    scanf("%d %d",&Q,&R);
    for(int i=0;i<Q;i++){
        new=H/2+1;
        arrh[new]=new*(new+1)/2;
        arrh[new-1]=new*(new-1)/2;
        scanf("%d %d",&temp1,&temp2);
        while(!(temp1>arrh[new-1]&&temp1<=arrh[new])){
            if(temp1<=arrh[new]){
                new=new/2;
            }
            else if(temp1>arrh[new]){
                new=new+new/2+1;
            }
            arrh[new]=new*(new+1)/2;
            arrh[new-1]=new*(new-1)/2;
        }
        hole=H+2-new;
        if(new>1)
            temp1=temp1-arrh[new-1];
        else if(new==1)
            temp1=1;
        for(int j=temp1;j<temp1+hole;j++){
            cnt[j]+=(float)temp2/(float)hole;
        }
    }
    for(int i=0;i<R;i++){
        ans=0;
        scanf("%d %d",&temp1,&temp2);
        for(int j=temp1;j<=temp2;j++){
            ans+=cnt[j];
        }
        printf("%.4f\n",ans);
    }
}

wider93 2년 전 0

40번 줄처럼 쭉 더하지 않는 법을 찾아야 합니다.

shjohw12 2년 전 0

시간복잡도가 O(R*H) 이므로 시간초과를 받을 수밖에 없습니다.

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

문제

문제

출처

ICPC

왜 시간초과가 나오는지 궁금합니다

marin663 2년 전 0

wider93 2년 전 0

shjohw12 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말