제출 #287394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
287394		infinite_iq	자리 배치 (IOI18_seats)	C++14	5 / 100	4102 ms	75128 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 [1009] ;
pi id [1000009] ;
vi tree [2][1009] ;
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