Submission #287425

#	Time	Username	Problem	Language	Result	Execution time	Memory
287425		infinite_iq	Seats (IOI18_seats)	C++14	5 / 100	4088 ms	62088 KiB

seats

    #include <bits/stdc++.h>
    using namespace std ;
    #define fi first 
    #define se second 
    #define mid (l+r)/2 
    #define le node*2 
    #define ri node*2+1
    typedef vector < int > vi ;
    typedef pair < int , int > pi ;
    #include "seats.h"
    int n , m ;
    vi a [10009] ;
    pi id [1000009] ;
    vi tree [2][10009] ;
    void upd ( int node , int l , int r , int t , int who , int id , int val ) {
            if ( l == r ) {
                    tree [t][who][node] = val ;
                    return ;
            }
            if ( id <= mid ) upd ( le , l , mid , t , who , id , val ) ;
            else upd ( ri , mid + 1 , r , t , who , id , val ) ;
            tree [t][who][node] = max ( tree [t][who][le] , tree [t][who][ri] ) ;
    }
    int query ( int node , int l , int r , int t , int who , int s , int e ) {
            if ( s > r || e < l ) return -1e9 ;
            if ( s <= l && e >= r ) return tree [t][who][node] ;
            return max ( query ( le , l , mid , t , who , s , e ) , query ( ri , mid + 1 , r , t ,who , s , e ) ) ;
    }
    int Mx ( int r1 , int r2 , int c1 , int c2 ) {
            if ( r1 > r2 ) swap ( r1 , r2 ) ;
            if ( c1 > c2 ) swap ( c1 , c2 ) ;
            if ( r1 < 0 || r2 >= n || c1 < 0 || c2 >= m ) return 1e9 ;
            int mx = 0 ;
            if ( r1 == r2 ) {
                    mx = query ( 1 , 0 , m-1 , 0 , r1 , c1 , c2 ) ;
            }
            if ( c1 == c2 ) {
                    mx = query ( 1 , 0 , n-1 , 1 , c1 , r1 , r2 ) ;
            }
            return mx ;
    }
    int solve () {
            int r1 , c1 , r2 , c2 , crnt = 0 , ans = 0 ;
            r1 = r2 = id [0].fi ;
            c1 = c2 = id [0].se ;
            while ( 1 ) {
                    ans += ( crnt == ( r2 - r1 + 1 ) * ( c2 - c1 + 1 ) - 1 ) ;
                    int val1 = Mx ( r1 - 1 , r1 - 1 , c1 , c2 ) ;
                    int val2 = Mx ( r1 , r2 , c2 + 1 , c2 + 1 ) ;
                    int val3 = Mx ( r2 + 1 , r2 + 1 , c1 , c2 ) ;
                    int val4 = Mx ( r1 , r2 , c1 - 1 , c1 - 1 ) ;
                    int best = min ( min ( val1 , val2 ) , min ( val3 , val4 ) ) ;
                    if ( best == 1e9 ) break ;
                    if ( best == val1 ) {
                            r1 -- ;
                            crnt = max ( crnt , val1 ) ;
                            continue ;
                    }
                    if ( best == val2 ) {
                            c2 ++ ;
                            crnt = max ( crnt , val2 ) ;
                            continue ;
                    }
                    if ( best == val3 ) {
                            r2 ++ ;
                            crnt = max ( crnt , val3 ) ;
                            continue ;
                    }
                    if ( best == val4 ) {
                            c1 -- ;
                            crnt = max ( crnt , val4 ) ;
                            continue ;
                    }
            }
            return ans ;
    }
    void give_initial_chart ( int H , int W , vi R, vi C) {
            n = H , m = W ;
            for ( int i = 0 ; i < n ; i ++ ) {
                    a [i] .resize (m) ;
            }
            for ( int i = 0 ; i < n * m ; i ++ ) {
                    a [R[i]][C[i]] = i ;
                    id [i] = { R [i] , C [i] } ;
            }
            for ( int i = 0 ; i < n ; i ++ ) {
                    tree [0][i] .resize ( 4*m , 0 ) ;
            }
            for ( int i = 0 ; i < m ; i ++ ) {
                    tree [1][i] .resize ( 4*n , 0 ) ;
            }
            for ( int i = 0 ; i < n ; i ++ ) {
                    for ( int j = 0 ; j < m ; j ++ ) {
                            upd ( 1 , 0 , m-1 , 0 , i , j , a [i][j] ) ;
                    }
            }
            for ( int j = 0 ; j < m ; j ++ ) {
                    for ( int i = 0 ; i < n ; i ++ ) {
                            upd ( 1 , 0 , n-1 , 1 , j , i , a [i][j] ) ;
                    }
            }
    }
    int swap_seats ( int x , int y ) {
            upd ( 1 , 0 , m-1 , 0 , id [x].fi , id [x].se , y ) ;
            upd ( 1 , 0 , n-1 , 1 , id [x].se , id [x].fi , y ) ;
            upd ( 1 , 0 , m-1 , 0 , id [y].fi , id [y].se , x ) ;
            upd ( 1 , 0 , n-1 , 1 , id [y].se , id [y].fi , x ) ;
            swap ( id [x] , id [y] ) ;
            return solve () ;
    }

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30