Submission #489607

#	Time	Username	Problem	Language	Result	Execution time	Memory
489607		pliam	Election (BOI18_election)	C++14	100 / 100	458 ms	28340 KiB

election

#include <bits/stdc++.h>
#define MAXN 500000
using namespace std;

int N,Q,a[MAXN];
struct node{
    int pref,suff,sum,ans;
};

node st[4*MAXN];

node merge(node nl,node nr){
    node n;
    n.pref=max(nl.pref,nl.sum+nr.pref);
    n.suff=max(nr.suff,nr.sum+nl.suff);
    n.sum=nl.sum+nr.sum;
    n.ans=max({nl.pref+nr.suff,nl.sum+nr.ans,nr.sum+nl.ans});
    return n;
}

//segment tree
void build(int v=1,int start=0,int end=N-1){
    if(start==end){
        st[v]={max(0,a[start]),max(0,a[start]),a[start],max(0,a[start])};
        return;
    }
    int mid=(start+end)/2;
    build(2*v,start,mid);
    build(2*v+1,mid+1,end);
    st[v]=merge(st[2*v],st[2*v+1]);
}

node query(int from,int to,int v=1,int start=0,int end=N-1){
    if(start==from&&end==to){
        return st[v];
    }
    int mid=(start+end)/2;
    if(to<=mid){
        return query(from,to,2*v,start,mid);
    }else if(from>mid){
        return query(from,to,2*v+1,mid+1,end);
    }else{
        return merge(query(from,mid,2*v,start,mid),query(mid+1,to,2*v+1,mid+1,end));
    }
}

int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        char c;
        scanf(" %c",&c);
        a[i]=(c=='C')?-1:1;
    }
    build();
    scanf("%d",&Q);
    for(int i=0;i<Q;i++){
        int l,r;
        scanf("%d %d",&l,&r);
        l--; r--;
        printf("%d\n",query(l,r).ans);
    }
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
election.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf(" %c",&c);
      |         ~~~~~^~~~~~~~~~
election.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
election.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%d %d",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~~

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