Submission #607102

#	Time	Username	Problem	Language	Result	Execution time	Memory
607102		chonka	Election (BOI18_election)	C++98	0 / 100	15 ms	23764 KiB

election

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 500007 ;

int n ;
string a ;

struct node {
    int sm , mn , mx ;
    node ( ) { sm = mn = mx = 0 ; }
    node ( int _sm , int _mn , int _mx ) { sm = _sm , mn = _mn , mx = _mx ; }
};
node tr[ 4 * MAXN ] ;



node unite ( node l , node r ) {
    node ret = node ( ) ;
    ret.sm = l.sm + r.sm ;
    ret.mn = min ( l.mn , l.sm + r.mn ) ;
    ret.mx = max ( l.mx , l.sm + r.mx ) ;
    return ret ;
}

void init ( int where , int IL , int IR ) {
    if ( IL == IR ) {
        if ( a[ IL - 1 ] == 'C' ) { tr[ where ] = node ( 1 , 0 , 1 ) ; }
        else { tr[ where ] = node ( -1 , -1 , 0 ) ; }
        return ;
    }
    int mid = ( IL + IR ) / 2 ;
    init ( 2 * where , IL , mid ) ;
    init ( 2 * where + 1 , mid + 1 , IR ) ;
    tr[ where ] = unite ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
}

node query ( int where , int IL , int IR , int CURL , int CURR ) {
    if ( IL > IR || CURL > CURR ) { return node ( ) ; }
    if ( IR < CURL || CURR < IL ) { return node ( ) ; }
    if ( CURL <= IL && IR <= CURR ) { return tr[ where ] ; }
    int mid = ( IL + IR ) / 2 ;
    return unite ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
}

void solve ( ) {
    cin >> n >> a ;
    init ( 1 , 1 , n ) ;
    int q ; cin >> q ;
    while ( q -- ) {
        int l , r ; cin >> l >> r ;
        node aux = query ( 1 , 1 , n , l , r ) ;
        cout << max ( -aux.mn , aux.mx - aux.sm ) << "\n" ;
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

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