Submission #288223

#	Time	Username	Problem	Language	Result	Execution time	Memory
288223		infinite_iq	Meetings (IOI18_meetings)	C++14	17 / 100	139 ms	14984 KiB

meetings

#include <bits/stdc++.h>
using namespace std ;
#define mid (l+r)/2
#define le node*2
#define ri node*2+1
#define pb push_back 
typedef long long ll ;
typedef vector < int > vi ;
typedef vector < ll > vll ;
const ll inf = 1e18 ;
#include "meetings.h"
ll n , q ;
ll h [100009] ;
struct NODE {
        ll pre , suf , ans , sz ;
} tree [400009] ;
NODE merge ( NODE x , NODE y ) {
        NODE ret ;
        ret .sz = x .sz + y .sz ;
        ret .ans = max ( x . ans , y .ans ) ;
        ret .pre = ( x .pre == x .sz ? x .pre + y .pre : x .pre ) ;
        ret .suf = ( y .suf == y .sz ? y .suf + x .suf : y .suf ) ;
        ret .ans = max ( ret .ans , x .suf + y .pre ) ;
        ret .ans = max ( ret .ans , max ( ret .pre , ret .suf ) ) ;
        return ret ;
}
void build ( int node , int l , int r ) {
        if ( l == r ) {
                int x = ( h [l] == 1 ) ;
                tree [node] = { x , x , x , 1 } ;
                return ;
        }
        build ( le , l , mid ) ;
        build ( ri , mid + 1 , r ) ;    
        tree [node] = merge ( tree [le] , tree [ri] ) ;
}
NODE query ( int node , int l , int r , int s , int e ) {
        if ( s <= l && e >= r ) return tree [node] ;
        if ( s <= mid && e >= mid + 1 ) return merge ( query ( le , l , mid , s , e ) , query ( ri , mid + 1 , r , s , e ) ) ;
        else if ( s <= mid ) return query ( le , l , mid , s , e ) ;
        else return query ( ri , mid + 1 , r , s , e ) ;
}
vll minimum_costs ( vi H , vi L , vi R) {
        n = H .size () , q = L .size () ;
        for ( ll i = 0 ; i < n ; i ++ ) {
                h [i] = H [i] ;
        }
        build ( 1 , 0 , n -1 ) ;
        vll ans ;
        for ( int i = 0 ; i < q ; i ++ ) {
                ll l = L [i] , r = R [i] ;
                ll sz = query ( 1 , 0 , n -1 , l , r ) .ans ;
                ll more = ( r - l + 1 ) - sz ;
                ans .pb ( sz + more * 2ll ) ;
        }
        return ans ;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40