글 읽기 - 세그먼트 트리 문제입니다 왜시간초과일까요?

ilsanzzang 6년 전 0

왜 시간초과가 나올까여

#include<iostream>
using namespace std;
const int maxN=200004;
int n,k,arr[maxN],base,a,b,st,tree[maxN*4];
char c;
void init(){
    base=1;
    while (base<n)
        base*=2;
    for(int i=0;i<n;i++){
        if(arr[i]<0)
            tree[base+i]=-1;
        else if(arr[i]>0)
            tree[base+i]=1;
        else
            tree[base+i]=0;
    }
    for(int i=n;i<base;i++)
        tree[base+i]=1;
    for(int i=base-1;i;i--)
        tree[i]=tree[i*2]*tree[i*2+1];
}
void update(){
    st=base+a-1;
    if(b>0)
        b=1;
    else if(b<0)
        b=-1;
    else
        b=0;
    if(tree[st]==b)
        return ;
    else{
        tree[st]=b;
        for(int i=st/2;i;i/=2)
            tree[i]=tree[i*2]*tree[i*2+1];
    }
}
void print(){
    a=a+base-1;
    b=b+base-1;
    int ret=1;
    while(a<=b){
        (a&1)?(ret*=tree[a],a=a/2+1):a/=2;
        (b&1)?b/=2:(ret*=tree[b],b=b/2-1);
        if(ret==0)
            break;
    }
    if(ret>0)
        cout<<"+";
    else if(ret<0)
        cout<<"-";
    else
        cout<<"0";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie();
    while(!cin.eof()){
        cin>>n>>k;
        for(int i=0;i<n;i++)
            cin>>arr[i];
        init();
        for(int i=0;i<k;i++){
            cin>>c>>a>>b;
            if(c=='C')
                update();
            else
                print();
        }
        cout<<"\n";
    }
}

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

문제

문제

출처

ICPC

세그먼트 트리 문제입니다 왜시간초과일까요?

ilsanzzang 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말