oj.uz

Submission #855019

# Submission time Handle Problem Language Result Execution time Memory
855019 2023-09-29T20:42:08 Z ivaziva Election (BOI18_election) C++14
0 / 100
 4 ms 6492 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXN 500010

long long n;
long long q;
string s;
long long pref1[MAXN];
long long pref2[MAXN];
long long seg1[MAXN*4];
long long seg2[MAXN*4];

void build1(long long node,long long l,long long r)
{
    if (l==r) seg1[node]=pref1[l];
    else
    {
        long long mid=(l+r)/2;
        build1(2*node,l,mid);
        build1(2*node+1,mid+1,r);
        seg1[node]=min(seg1[2*node],seg1[2*node+1]);
    }
}

void build2(long long node,long long l,long long r)
{
    if (l==r) seg2[node]=pref2[l];
    else
    {
        long long mid=(l+r)/2;
        build2(2*node,l,mid);
        build2(2*node+1,mid+1,r);
        seg2[node]=min(seg2[2*node],seg2[2*node+1]);
    }
}

long long get1(long long node,long long l,long long r,long long a,long long b)
{
    if (a>b) return LLONG_MAX;
    else if (l==a and r==b) return seg1[node];
    long long mid=(l+r)/2;
    return min(get1(2*node,l,mid,a,min(b,mid)),get1(2*node+1,mid+1,r,max(a,mid+1),b));
}

long long get2(long long node,long long l,long long r,long long a,long long b)
{
    if (a>b) return LLONG_MAX;
    else if (l==a and r==b) return seg2[node];
    long long mid=(l+r)/2;
    return min(get2(2*node,l,mid,a,min(b,mid)),get2(2*node+1,mid+1,r,max(a,mid+1),b));
}

int main()
{
    ios_base::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>s;
    pref1[0]=0;
    for (long long i=1;i<=n;i++)
    {
        if (s[i-1]=='C') pref1[i]=pref1[i-1]+1;
        else pref1[i]-pref1[i-1]-1;
    }
    pref2[n+1]=0;
    for (long long i=n;i>=1;i--)
    {
        if (s[i-1]=='C') pref2[i]=pref2[i+1]+1;
        else pref2[i]=pref2[i+1]-1;
    }
    build1(1,1,n);
    build2(1,1,n);
    cin>>q;
    for (long long i=1;i<=q;i++)
    {
        long long l,r;
        cin>>l>>r;
        long long d1=get1(1,1,n,l,r)-pref1[l-1];
        long long d2=get2(1,1,n,l,r)-pref2[r+1];
        if (d1>=0 and d2>=0) cout<<0<<endl;
        else if (d1>=0 and d2<0) cout<<abs(d2)<<endl;
        else if (d1<0 and d2>=0) cout<<abs(d1)<<endl;
        else cout<<max(abs(d1),abs(d2))<<endl;
    }
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:66:33: warning: statement has no effect [-Wunused-value]
   66 |         else pref1[i]-pref1[i-1]-1;
      |              ~~~~~~~~~~~~~~~~~~~^~

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -