Submission #297968

#	Time	Username	Problem	Language	Result	Execution time	Memory
297968		muhammad_hokimiyon	Seats (IOI18_seats)	C++14	100 / 100	3508 ms	150520 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000007;

int h,w;
int t[4 * maxn];
int lz[4 * maxn];
int mn[4 * maxn];
vector < vector < int > > a;

int comb( int x1 , int x2 )
{
    if( mn[x1] == mn[x2] ){
        return t[x1] + t[x2];
    }
    if( mn[x1] < mn[x2] ){
        return t[x1];
    }
    return t[x2];
}

void push( int x )
{
    lz[x + x] += lz[x];
    lz[x + x + 1] += lz[x];
    mn[x + x] += lz[x];
    mn[x + x + 1] += lz[x];
    lz[x] = 0;
}

void build( int x , int l , int r )
{
    t[x] = r - l + 1;
    if( l == r )return;
    int m = (l + r) / 2;
    build( x + x , l , m );
    build( x + x + 1 , m + 1 , r );
}

void upd( int x , int l , int r , int tl , int tr , int val )
{
    if( tl > tr )return;
    if( tl == l && tr == r ){
        lz[x] += val;
        mn[x] += val;
        return;
    }
    int m = (l + r) / 2;
    push( x );
    upd( x + x , l , m , tl , min( tr , m ) , val );
    upd( x + x + 1 , m + 1 , r , max( tl , m + 1 ) , tr , val );
    t[x] = comb( x + x , x + x + 1 );
    mn[x] = min( mn[x + x] , mn[x + x + 1] );
}

void ok( int i , int j , int val )
{
    if( i > h || j > w )return;
    vector < int > g;
    g.push_back(a[i][j]);
    g.push_back(a[i - 1][j]);
    g.push_back(a[i][j - 1]);
    g.push_back(a[i - 1][j - 1]);
    sort( g.begin() , g.end() );
    if( a[i][j] < min( a[i - 1][j] , a[i][j - 1] ) ){
        upd( 1 , 1 , h * w , a[i][j] , min( a[i - 1][j] , a[i][j - 1] ) - 1 , val );
    }
    upd( 1 , 1 , h * w , g[2] , g[3] - 1 , val );
}

vector < int > r,c;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
    h = H;
    w = W;
    r = R;
    c = C;
    build( 1 , 1 , h * w );
    a.resize(H + 10);
    for( int i = 0; i < H + 10; i++ ){
        a[i].resize(W + 10);
    }
    for( int i = 0; i < W + 10; i++ ){
        a[0][i] = a[h + 1][i] = h * w + 1;
    }
    for( int i = 0; i < H + 10; i++ ){
        a[i][0] = a[i][W + 1] = h * w + 1;
    }
    for( int i = 0; i < H * W; i++ ){
        a[R[i] + 1][C[i] + 1] = i + 1;
    }
    for( int i = 1; i <= H; i++ ){
        for( int j = 1; j <= W; j++ ){
            ok( i , j , 1 );
        }
    }
}

int swap_seats(int a1, int b)
{
    int x1 = r[a1] + 1;
    int y1 = c[a1] + 1;
    int x2 = r[b] + 1;
    int y2 = c[b] + 1;
    vector < pair < int , int > > g;
    for( int i = 0; i <= 1; i++ ){
        for( int j = 0; j <= 1; j++ ){
            g.push_back({ i + x1 , j + y1 });
            g.push_back({ i + x2 , j + y2 });
        }
    }
    sort( g.begin() , g.end() );
    g.erase( unique( g.begin() , g.end() ) , g.end() );
    for( auto x : g )ok( x.first , x.second , -1 );
    swap( a[r[a1] + 1][c[a1] + 1] , a[r[b] + 1][c[b] + 1] );
    swap( r[a1] , r[b] );
    swap( c[a1] , c[b] );
    for( auto x : g )ok( x.first , x.second , 1 );
    return t[1];
}

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