Submission #138366

#	Time	Username	Problem	Language	Result	Execution time	Memory
138366		CaroLinda	Seats (IOI18_seats)	C++14	Compilation error	0 ms	0 KiB

seats

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

#define debug 
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int MAXN = 1e6+10 ;
const int MAX = 1010 ;
const int inf=1e9+10 ;

using namespace std ;

struct Seg
{

    pii v[MAXN*4] ;

    int m(int l, int r) { return (l+r)/2 ; }

    pii merge( pii x , pii y ) { return mk( min(x.ff, y.ff) , max(x.ss,y.ss) ) ; }

    void upd(int pos, int l, int r, int x , int val)
    {

        if(l==r)
        {
            v[pos] = mk(val,val) ;
            return ;
        }


        if( x <= m(l,r) ) upd(pos*2, l, m(l,r) , x , val) ;
        else upd(pos*2+1, m(l,r)+1 , r , x , val) ;


        v[pos] = merge( v[pos*2] , v[pos*2+1] ) ;

    }

    pii query( int pos , int l , int r , int en )
    {

        if( l > en ) return mk( inf , -inf ) ;
        if( r <= en ) return v[pos] ;

        pii al = query(pos*2, l , m(l,r) , en) ;
        pii ar = query(pos*2+1, m(l,r)+1 , r  ,en ) ;

        return merge(al,ar) ;

    }

    void print(int pos, int l, int r)
    {
        debug("%d %d -> %d %d\n" , l , r , v[pos].ff ,v[pos].ss) ;
        if(l==r) return ;
        print(pos*2,l,m(l,r)) ;
        print(pos*2+1,m(l,r)+1,r) ;
    }

} ;

int n ;

pii p[MAXN] ;

Seg r , c ;

// ------------------------------------


int swap_seats(int a , int b )
{

    swap(p[a] , p[b] ) ;
    r.upd( 1,0,n-1,a,p[a].ff ) ;
    r.upd(1,0,n-1,b,p[b].ff) ;
    c.upd(1,0,n-1,a,p[a].ss) ;
    c.upd( 1 , 0, n-1 , b , p[b].ss ) ;

    int ans = 0 ;

    lp(i,0,n)
    {

        pii curAux , curMin , curMax ;

        curAux = r.query( 1 , 0 , n-1 , i ) ;

        curMin.ff = curAux.ff ;
        curMax.ff = curAux.ss ;

        curAux = c.query(1,0,n-1,i) ;

        curMin.ss = curAux.ff ;
        curMax.ss = curAux.ss ;

        int grid = ( curMax.ff - curMin.ff + 1 ) * ( curMax.ss - curMin.ss + 1 ) ;

        if( grid == i+1 ) ans ++ ;
        
        else i = grid-2 ;

    }

    return ans ;

}

void give_initial_chart(int h , int w , vector<int> R , vector<int> C )
{
    n = R.size() ;

    lp(i,0,n) p[i] = mk( R[i] , C[i] ) ;
    lp(i,0,n) 
    {
        r.upd( 1 , 0 , n-1 , i , p[i].ff ) ;
        c.upd(1,0,n-1,i,p[i].ss) ;
    }
    
}

Compilation message (stderr)

Compilation timeout while compiling seats