글 읽기 - 반례를 못찾겠습니다.

cs71107 5년 전 0

다음과 같은 소스 코드로 이 문제를 풀어보려고 했는데, 자꾸 틀렸다고 나와요... 반례좀 찾아주세요.

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000;
const long long int INF = 10000000000;

int n,base=1;

long long int mintree[3*MAXN+1],maxtree[3*MAXN+1];

long long int A[MAXN+1];

long long int msearch(int L,int R,bool ismin)
{
    bool judge = false;
    if(R<base)return 0;
    if(L<base){L = base; judge = true;}
    long long int ans;
    if(ismin)ans = INF;
    else ans = -INF;

    while(L<=R){
        if(L%2){
            if(ismin)ans = min(ans,mintree[L]);
            else ans = max(ans,maxtree[L]);
        }
        if(!(R%2)){
            if(ismin)ans = min(ans,mintree[R]);
            else ans = max(ans,maxtree[R]);
        }
        L++; R--;
        L/=2; R/=2;
    }
    if(judge&&ismin)ans = min(ans,0LL);
    else if(judge)ans = max(ans,0LL);
    return ans;
}

int main()
{

    scanf("%d",&n);
    for(;base<n;base*=2);

    for(int i=1;i<=n;i++){
            scanf("%lld",&A[i]);
            A[i]+=A[i-1];
            mintree[base+i-1] = A[i];
            maxtree[base+i-1] = A[i];
    }

    for(int i=base+n;i<base*2;i++){
        mintree[i] = INF;
        maxtree[i] = -INF;
    }

    for(int i=base-1;i>=1;i--){
        mintree[i] = min(mintree[i*2],mintree[i*2+1]);
        maxtree[i] = max(maxtree[i*2],maxtree[i*2+1]);
    }
    int m;
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        int x1,x2,y1,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x1 += (base-1);
        y1 += (base-1);
        x2 += (base-1);
        y2 += (base-1);
        long long int minv = msearch(x1-1,y1-1,true);
        long long int maxv = msearch(x2,y2,false);
        printf("%lld\n",maxv-minv);
    }

    return 0;
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.

cs71107 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말