Submission #287518

#	Time	Username	Problem	Language	Result	Execution time	Memory
287518		infinite_iq	Seats (IOI18_seats)	C++14	25 / 100	4093 ms	73720 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]  ;
pair < pi , pi > tree [4000009] ;
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 upd ( int node , int l , int r , int id ) {
        if ( l == r ) {
                tree [node] = { { a [l] , a [l] } , { b [l] , b [l] } } ;
                return ;
        }
        if ( id <= mid ) upd ( le , l , mid , id ) ;
        else upd ( ri , mid + 1 , r , id ) ;
        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] ;
                upd ( 1 , 0 , N -1 , i ) ;
        }
}
int swap_seats ( int x , int y ) {
        swap ( a [x] , a [y] ) ;
        swap ( b [x] , b [y] ) ;
        upd ( 1 , 0 , N - 1 , x ) ;
        upd ( 1 , 0 , N - 1 , y ) ;
        int r1 = 1e9 , r2 = 0 , c1 = 1e9 , c2 = 0 , ans = 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] ) ;
                if ( ( r2 - r1 + 1 ) * ( c2 - c1 + 1 ) == i + 1 ) {
                        ans ++ ;
                        continue ;
                }
                int to = ( r2 - r1 + 1 ) * ( c2 - c1 + 1 ) - 1 ;
                pair < pi , pi > info = query ( 1 , 0 , N -1 , i , to ) ;
                r1 = min ( r1 , info .fi.fi ) ;
                r2 = max ( r2 , info .fi.se ) ;
                c1 = min ( c1 , info .se.fi ) ;
                c2 = max ( c2 , info .se.se ) ;
                i = to - 1 ;
        }
        return ans ;
}

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