oj.uz

답안 #481164

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
481164 2021-10-19T16:23:18 Z Karabasan Election (BOI18_election) C++17
0 / 100
 2 ms 344 KB 
#include <bits/stdc++.h>

using namespace std;
int n;
string s;
int dizi1[500005];
int dizi2[500005];
int seg1[2000005];
int seg2[2000005];
int segment(int x,int l,int r,int bas,int son)
{
    if(r<bas||l>son)
        return 0;
    if(l>=bas&&r<=son)
        return seg1[x];
    int orta=(l+r)/2;
    return max(segment(x*2,l,orta,bas,son),segment(x*2+1,orta+1,r,bas,son));
}
int segment2(int x,int l,int r,int bas,int son)
{
    if(r<bas||l>son)
        return 0;
    if(l>=bas&&r<=son)
        return seg2[x];
    int orta=(l+r)/2;
    return max(segment2(x*2,l,orta,bas,son),segment2(x*2+1,orta+1,r,bas,son));
}
int build2(int x,int bas,int son)
{
    if(bas==son)
        return seg2[x]=dizi2[bas];
    int orta=(bas+son)/2;
    seg2[2*x]=build2(2*x,bas,orta);
    seg2[2*x+1]=build2(2*x+1,orta+1,son);
        return seg2[x]=max(seg2[2*x],seg2[2*x+1]);

}
int build(int x,int bas,int son)
{
    if(bas==son)
        return seg1[x]=dizi1[bas];
    int orta=(bas+son)/2;
    seg1[2*x]=build(2*x,bas,orta);
    seg1[2*x+1]=build(2*x+1,orta+1,son);
        return seg1[x]=max(seg1[2*x],seg1[2*x+1]);

}
int main()
{
    scanf("%d",&n);
    cin>>s;
    s="U"+s;
    if(s[1]=='C')
        dizi1[1]=-1;
    else dizi1[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(s[i]=='C')
            dizi1[i]=dizi1[i-1]-1;
        else dizi1[i]=dizi1[i-1]+1;
    }
    if(s[n]=='C')
        dizi2[n]=-1;
    else dizi2[n]=1;
    for(int i=n-1;i>=0;i--)
    {
        if(s[i]=='C')
            dizi2[i]=dizi2[i+1]-1;
        else dizi2[i]=dizi2[i+1]+1;
    }
    build(1,1,n);
    build2(1,1,n);
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",max(segment(1,1,n,a,b)-dizi1[a-1],segment2(1,1,n,a,b)-dizi2[b+1]));
    }
    return 0;
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
election.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
election.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -