BOJ 5676(음주 코딩)풀이

solved.ac 티어 : 골드 1

www.acmicpc.net/problem/5676

5676번: 음주 코딩

문제를 보면 바로 구간 곱이라는 것을 알 수 있다 하지만 구간 곱을 구현한 뒤 제출하면 시간 초과를 받는다.

이유는 값이 너무 커져서 그런것인데 어차피 값을 원하는 게 아니라 부호만 알면 되는 거기 때문에 음수일 경우 -1을 곱하고 양수일 경우 1, 0일 경우 0을 곱해주면 된다. 출력에서도 구간 곱이 양수면 +, 음수면 -,0이면 0을 출력해주면 된다.

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
vector<long long>l(1000001);
ll seg(vector<long long>&tree,ll n,ll s,ll e){
    if(s==e){
        if(l[s]==0)return tree[n]=0;
        else if(l[s]>0)return tree[n]=1;
        else return tree[n]=-1;
    }
    return tree[n]=seg(tree,n*2,s,(s+e)/2)*seg(tree,n*2+1,(s+e)/2+1,e);
}
ll max1(vector<long long>&tree,ll n,ll s,ll e,ll left,ll right){
    if(left>e||right<s){return 1;}
    if(left<=s&&e<=right){return tree[n];}
    return max1(tree,n*2,s,(s+e)/2,left,right)*max1(tree,n*2+1,(s+e)/2+1,e,left,right);
}
ll change(vector<long long>&tree,ll n,ll s,ll e,ll i,ll f){
    if(i<s||i>e){return tree[n];}
    if(s==e){
        if(f==0)return tree[n]=0;
        else if(f>0)return tree[n]=1;
        else return tree[n]=-1;
    }
    return tree[n]=change(tree,n*2,s,(s+e)/2,i,f)*change(tree,n*2+1,(s+e)/2+1,e,i,f);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    ll a,b,c,d,q,k,gh,av;
    //for(int iii=0;iii<4;iii++){
    while(1){
        cin >> a >> b;
        if(cin.eof() == true)break;
        int h=(int)ceil(log2(a));
        int tree_size=(1<<(h+1)),i;
        vector<long long>tree(tree_size);
        for(i=0;i<a;i++){cin >> l[i];}
        seg(tree,1,0,a-1);
        for(i=0;i<b;i++){
            char asd;
            cin >> asd;
            if(asd=='C'){
                cin >> c >> d;
                change(tree,1,0,a-1,c-1,d);
            }else{
                cin >> c >> d;
                av=max1(tree,1,0,a-1,c-1,d-1);
                if(av==0)cout << '0';
                else if(av>0)cout << '+';
                else cout << '-';
            }
        }
        cout << '\n';
    }
}