Submission #97368

#	Time	Username	Problem	Language	Result	Execution time	Memory
97368		georgerapeanu	Election (BOI18_election)	C++11	0 / 100	3 ms	384 KiB

election

#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 5e5;
const int QMAX = 5e5;

int n,q;
int pref[NMAX + 5];
char c[NMAX + 5];
pair<int,int> aint[4 * NMAX + 5];

pair<int,int> join(pair<int,int> a,pair<int,int> b){
    pair<int,int> ans = {-1,-1};

    if(a.first == -1 || b.first == -1){
        ans.first = -1 ^ a.first ^ b.first;
        ans.second = -1 ^ a.second ^ b.second;
    }
    else{
        ans.first = (pref[a.first] < pref[b.first] ? a.first:b.first);
        ans.second = (pref[a.second] > pref[b.second] ? a.second:b.second);
    }

    return ans;
}

void build(int nod,int st,int dr){
    if(st == dr){
        aint[nod] = {st,st};
        return ;
    }

    int mid = (st + dr) / 2;

    build(nod * 2,st,mid);
    build(nod * 2 + 1,mid + 1,dr);

    aint[nod] = join(aint[nod * 2],aint[nod * 2 + 1]);
}

pair<int,int> query(int nod,int st,int dr,int S,int D){
    if(dr < S || st > D){
        return {-1,-1};
    }

    if(S <= st && dr <= D){
        return aint[nod];
    }

    int mid = (st + dr) / 2;
    pair<int,int> a = query(nod * 2,st,mid,S,D);
    pair<int,int> b = query(nod * 2 + 1,mid + 1,dr,S,D);


    return join(a,b);
}

int main(){
    
    scanf("%d\n",&n);
    fgets(c + 1,NMAX + 5,stdin);
    scanf("%d",&q);

    for(int i = 1; i <= n;  i++){
        pref[i] = pref[i - 1] + (c[i] == 'C' ? 1:-1);
    }

    build(1,1,n);

    while(q--){
        int l,r;
        scanf("%d %d",&l,&r);
        int ma = query(1,1,n,l,r).second;
        int mi1 = query(1,1,n,l,ma).first;
        int mi2 = query(1,1,n,ma,r).first;
        int ma_val = pref[ma] - pref[l - 1];
        int mi1_val = pref[mi1] - pref[l - 1];
        int mi2_val = pref[mi2] - pref[l - 1];
        int r_val = pref[r] - pref[l - 1];

        int ans = 0;

        ans += max(0,-mi1_val);
        ans += ma_val - r_val;
        ans += max(0,(mi2_val <= mi1_val && mi2_val <= 0) * (min(0,mi1_val) - mi2_val) - (ma_val - r_val));

        printf("%d\n",ans);
    }
    
    
    return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n",&n);
     ~~~~~^~~~~~~~~~~
election.cpp:63:10: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fgets(c + 1,NMAX + 5,stdin);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
election.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
election.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&l,&r);
         ~~~~~^~~~~~~~~~~~~~~
In file included from /usr/include/stdio.h:936:0,
                 from /usr/include/c++/7/cstdio:42,
                 from election.cpp:1:
In function 'char* fgets(char*, int, FILE*)',
    inlined from 'int main()' at election.cpp:63:10:
/usr/include/x86_64-linux-gnu/bits/stdio2.h:261:58: warning: call to '__fgets_chk_warn' declared with attribute warning: fgets called with bigger size than length of destination buffer
  return __fgets_chk_warn (__s, __bos (__s), __n, __stream);
                                                          ^

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18