oj.uz

Submission #607127

# Submission time Handle Problem Language Result Execution time Memory
607127 2022-07-26T12:20:40 Z chonka Election (BOI18_election) C++
100 / 100
 689 ms 42916 KB 
#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 , pref , suff ;
    int ans = 0 ;
    node ( ) { sm = pref = suff = 0 ; }
    node ( int _sm , int _pref , int _suff ) {
        sm = _sm , pref = _pref , suff =_suff ;
        ans = min ( pref , suff ) ;
    }
};
node tr[ 4 * MAXN ] ;



node unite ( node l , node r ) {
    node ret = node ( ) ;
    ret.sm = l.sm + r.sm ;

    ret.ans = l.pref + r.suff ;
    ret.ans = min ( ret.ans , l.ans + r.sm ) ;
    ret.ans = min ( ret.ans , r.ans + l.sm ) ;
    
    ret.pref = min ( l.pref , l.sm + r.pref ) ;
    ret.suff = min ( r.suff , r.sm + l.suff ) ;
    return ret ;
}

void init ( int where , int IL , int IR ) {
    if ( IL == IR ) {
        if ( a[ IL - 1 ] == 'C' ) { tr[ where ] = node ( 1 , 0 , 0 ) ; }
        else { tr[ where ] = node ( -1 , -1 , -1 ) ; }
        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 << -aux.ans << "\n" ;
    }
}

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

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31572 KB Output is correct
2 Correct 23 ms 31560 KB Output is correct
3 Correct 25 ms 31764 KB Output is correct
4 Correct 16 ms 31604 KB Output is correct
5 Correct 18 ms 31564 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31572 KB Output is correct
2 Correct 23 ms 31560 KB Output is correct
3 Correct 25 ms 31764 KB Output is correct
4 Correct 16 ms 31604 KB Output is correct
5 Correct 18 ms 31564 KB Output is correct
6 Correct 70 ms 33024 KB Output is correct
7 Correct 85 ms 32844 KB Output is correct
8 Correct 81 ms 32908 KB Output is correct
9 Correct 83 ms 32924 KB Output is correct
10 Correct 85 ms 32872 KB Output is correct
11 Correct 75 ms 33000 KB Output is correct
12 Correct 99 ms 33088 KB Output is correct
13 Correct 74 ms 33012 KB Output is correct
14 Correct 76 ms 33072 KB Output is correct
15 Correct 68 ms 32988 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31572 KB Output is correct
2 Correct 23 ms 31560 KB Output is correct
3 Correct 25 ms 31764 KB Output is correct
4 Correct 16 ms 31604 KB Output is correct
5 Correct 18 ms 31564 KB Output is correct
6 Correct 70 ms 33024 KB Output is correct
7 Correct 85 ms 32844 KB Output is correct
8 Correct 81 ms 32908 KB Output is correct
9 Correct 83 ms 32924 KB Output is correct
10 Correct 85 ms 32872 KB Output is correct
11 Correct 75 ms 33000 KB Output is correct
12 Correct 99 ms 33088 KB Output is correct
13 Correct 74 ms 33012 KB Output is correct
14 Correct 76 ms 33072 KB Output is correct
15 Correct 68 ms 32988 KB Output is correct
16 Correct 652 ms 41876 KB Output is correct
17 Correct 626 ms 41372 KB Output is correct
18 Correct 565 ms 41756 KB Output is correct
19 Correct 555 ms 41244 KB Output is correct
20 Correct 630 ms 41024 KB Output is correct
21 Correct 684 ms 42780 KB Output is correct
22 Correct 623 ms 42604 KB Output is correct
23 Correct 670 ms 42916 KB Output is correct
24 Correct 689 ms 42452 KB Output is correct
25 Correct 595 ms 41984 KB Output is correct