글 읽기 - 시간초과 의심되는 부분이 두가지가있는데 잘 모르겠습니다

cdt416z 4년 전 0

세그먼트 트리로 문제를 풀었는데

시간초과로 예상되는 부분이 두가지가 있습니다..

하나는 OR연산인데

OR연산 자체를 61번 줄과같이 하면 수행시간이 더 늘어나는지 궁금합니다

두번째는 reseg()함수를 범위가 아니라 하나하나씩 해주고있다는건데

reseg 함수를 범위에 맞춰서 한번에 할 수 있는지도 궁금합니다..

#include <stdio.h>

int line[250001];
int Tree[1000001];
int N, K, M;
int l, r, x;

int segment(int root, int left, int right){
    if(left == right){
        if(line[left] == K){
            Tree[root] = 1;
        }
        else{
            Tree[root] = 0;
        }
    }
    else{
        int mid = (left + right) / 2;
        Tree[root] = segment(root * 2, left, mid) + segment(root * 2 + 1, mid + 1, right);
    }
    return Tree[root];
}

int find(int start, int end, int root, int left, int right){
    if(start <= left && right <= end){
        return Tree[root];
    }
    if(start > right || end < left){
        return 0;
    }
    int mid = (left + right) / 2;
    return find(start, end, root * 2, left, mid) + find(start, end, root * 2 + 1, mid + 1, right);
}

void reseg(int diff, int index, int root, int left, int right){
    if(index > right || index < left){
        return;
    }
    Tree[root] = Tree[root] + diff;
    int mid = (left + right) / 2;
    if(left != right){
        reseg(diff, index, root * 2, left, mid);
        reseg(diff, index, root * 2 + 1, mid + 1, right);
    }
}

int main(){
    scanf("%d %d", &N, &K);
    for(int i = 1; i <= N; i++){
        scanf("%d", &line[i]);
    }
    segment(1, 1, N);
    scanf("%d", &M);
    for(int i = 0; i < M; i++){
        int choice;
        scanf("%d", &choice);
        if(choice == 1){
            scanf("%d %d %d", &l, &r, &x);
            for(int k = l; k <= r; k++){
                int temp = line[k];
                line[k] = line[k] | x;
                if(temp == K && line[k] != K){
                    reseg(-1, k, 1, 1, N);
                }
                else if(temp != K && line[k] == K){
                    reseg(1, k, 1, 1, N);
                }
            }
        }
        else{
            scanf("%d %d", &l, &r);
            int result = find(l, r, 1, 1, N);
            printf("%d\n", result);
        }
    }
    return 0;
}

blackking26 4년 전 0

57~69 line의 if문은 최대 M번 실행되고 그 if문 한 번 당 69~68 line의 for문이 최대 N번 시행되므로 시간복잡도가 적어도 O(NM)인 것 같습니다.

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

문제

문제

출처

ICPC

시간초과 의심되는 부분이 두가지가있는데 잘 모르겠습니다

cdt416z 4년 전 0

blackking26 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말