Submission #287502

#	Time	Username	Problem	Language	Result	Execution time	Memory
287502		infinite_iq	Seats (IOI18_seats)	C++14	17 / 100	4091 ms	59512 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 , n , m , crnt ;
int a [1000009] , b [1000009] , ans [1000009] ;
pair < pi , pi > info [1000009] ;
pair < pi , pi > tree [400009] ;
pair < pi , pi > merge ( pair < pi ,pi > x , pair < pi , pi > y ) {
        pair < pi , pi > ret ;
        ret .fi.fi = min ( x .fi.fi , y .fi.fi ) ;
        ret .fi.se = max ( x .fi.se , y .fi.se ) ;
        ret .se.fi = min ( x .se.fi , y .se.fi ) ;
        ret .se.se = max ( x .se.se , y .se.se ) ;
        return ret ;
}
void build ( int node , int l , int r ) {
        if ( l == r ) {
                tree [node] = { { a [l] , a [l] } , { b [l] , b [l] } } ;
                return ;
        }
        build ( le , l , mid ) ;
        build ( ri , mid + 1 , r ) ;
        tree [node] = merge ( tree [le] , tree [ri] ) ;
}
pair < pi , pi > query ( int node , int l , int r , int s , int e ) {
        if ( s > r || e < l ) return { { 1e9 , 0 } , { 1e9 , 0 } } ;
        if ( s <= l && e >= r ) return tree [node] ;
        return merge ( query ( le , l , mid , s , e ) , query ( ri , mid + 1 , r , s , e ) ) ;
}
void give_initial_chart ( int H , int W , vi R, vi C ) {
        n = H , m = W , N = n * m ;
        for ( int i = 0 ; i < N ; i ++ ) {
                a [i] = R [i] ;
                b [i] = C [i] ;
        }
        int r1 = 1e9 , r2 = 0 , c1 = 1e9 , c2 = 0 ;
        for ( int i = 0 ; i < N ; i ++ ) {
                r1 = min ( r1 , a [i] ) ;
                r2 = max ( r2 , a [i] ) ;
                c1 = min ( c1 , b [i] ) ;
                c2 = max ( c2 , b [i] ) ;
                info [i] = { { r1 , r2 } , { c1 , c2 } } ;
                ans  [i] = ( ( r2 - r1 + 1 ) * ( c2 - c1 + 1 ) == i + 1 ) ;
                crnt += ans [i] ; 
        }
//      build ( 1 , 0 , N - 1 ) ;
}
int swap_seats ( int x , int y ) {
        swap ( a [x] , a [y] ) ;
        swap ( b [x] , b [y] ) ;
        if ( x > y ) swap ( x , y ) ;
        int r1 = ( x ? info [x-1].fi.fi : 1e9 ) ;
        int r2 = ( x ? info [x-1].fi.se : 0   ) ;
        int c1 = ( x ? info [x-1].se.fi : 1e9 ) ;
        int c2 = ( x ? info [x-1].se.se : 0   ) ;
        for ( int i = x ; i <= y ; i ++ ) {
                r1 = min ( r1 , a [i] ) ;
                r2 = max ( r2 , a [i] ) ;
                c1 = min ( c1 , b [i] ) ;
                c2 = max ( c2 , b [i] ) ;
                info [i] = { { r1 , r2 } , { c1 , c2 } } ;
                crnt -= ans [i] ;
                ans  [i] = ( ( r2 - r1 + 1 ) * ( c2 - c1 + 1 ) == i + 1 ) ;
                crnt += ans [i] ;
        }
        return crnt ;
}

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