글 읽기 - 반례가 필요합니다

imscs22 5년 전 0

정확히는 99% 에서 틀리네요

뭐 틀린건 틀린거지만,일단 소스를 간단히 설명하면

zeros배열은 해당 범위의 실제 0의 갯수의 합을 나타내는 펜윅트리(함수 zup,sum,getZ)

메인의 tree배열은 0일때를 1과의 곱으로 변환해 곱을 나타내는 펜윅트리(함수 update,getR,mul)

d배열은 각 위치의 데이터를 순수하게 저장만 하는 배열입니다

0의 갯수가 업뎃될때는 !0 ---> 0 이나 0 ---> !0 일때만 변화합니다

최종답은 일단 해당범위의 0의 갯수를 검사하고 갯수가 0이면 +인지-인지 검사합니다

#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>
#include <cstdio>
using namespace std;
double max(double x,double y){
    return x>y?x:y;
}
void update(vector<double>& tree,int pos,double diff){
    for(int i=pos;i<tree.size();i+=i&-i){
        tree[i]*=diff;
    }
}
double getR(vector<double>& tree,int r){
    double rst =1.0;
    for(;r;r-=r&-r){
        rst*=tree[r];
    }
    return rst;
}

double mul(vector<double>& tree,int s,int e){
    if(s>e){
        return mul(tree,e,s);
    }else
    return getR(tree,e)/getR(tree,s-1);
}
void zup(vector<int>& tree,int pos,int diff){
    for(int i=pos;i<tree.size();i+=i&-i){
        tree[i]+=diff;
    }
}
int getZ(vector<int>& tree,int z){
    int rst =0;
    for(;z;z-=z&-z){
        rst+=tree[z];
    }
    return rst;
}
int sum(vector<int>& tree,int s,int e){
    if(s>e){
        return sum(tree,e,s);
    }else
        return getZ(tree,e)-getZ(tree,s-1);
}
int main(){
    //ofstream osm("./output5676.txt");
    while(cin){
        int n,k;
        cin>>n>>k;
        vector<double> tree(n+3,1);
        vector<int> zero(n+3,0);
        vector<int> d(n+3);
        for(int i=1;i<=n;i++){
            cin>>d[i];
            if(d[i])
            update(tree,i,d[i]);
            else{
                zup(zero,i,1);
            }
        }
        for(int i=0;i<k;i++){
            char c;
            cin>>c;
            if(c=='C'){
                int p,v;
                cin>>p>>v;
                if(!v){
                    if(d[p]){
                        const double diff = (double)1/d[p];
                        d[p]=v;
                        update(tree,p,diff);
                        zup(zero,p,1);
                    }
                }else{
                    if(!d[p]){
                        zup(zero,p,-1);
                    }
                    const double diff = d[p]?(double)v/d[p]:v;
                    d[p]=v;
                    update(tree,p,diff);
                }
            }
            else if(c=='P'){
                int s,e;
                cin>>s>>e;
                const double det = mul(tree,s,e);
                const int zeros = sum(zero,s,e);
                if(!det||zeros){
                    cout<<0;
                }
                else if(det>0){
                    cout<<'+';
                }
                else if(det<0){
                    cout<<'-';
                }
            }
        }
        cout<<endl;
    }
    return 0;
}

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

문제

문제

출처

ICPC

반례가 필요합니다

imscs22 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말