Submission #138223

#	Time	Username	Problem	Language	Result	Execution time	Memory
138223		CaroLinda	Seats (IOI18_seats)	C++14	11 / 100	756 ms	33412 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 = 1e4+10 ;
const int inf=1e9+10 ;

using namespace std ;

struct Rectangle
{

	int r1 , c1 , r2 , c2 ;

	Rectangle( int r1 = 0 , int c1 = 0 , int r2 = 0 , int c2 = 0 )
		: r1(r1) , c1(c1) , r2(c2) , c2(c2) {}

} ;

int n , globalAns ;

int isRectangle[MAXN] ;

pii p[MAXN] ;

pair<pii,pii> rec[MAXN] ;

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



int swap_seats(int a , int b)
{

	swap(p[a] , p[b]) ;

	if(b<a) swap(a,b) ;

	pii p1 = ( a == 0 ? mk(inf,inf) : rec[a-1].ff ) ;
	pii p2 = ( a == 0 ? mk(-1,-1) : rec[a-1].ss ) ;

	lp(i,a,b+1)
	{

		pii cur = p[i] ;

		p1 = mk( min(p1.ff,cur.ff) , min(p1.ss, cur.ss) ) ;
		p2 = mk( max(p2.ff, cur.ff) , max(p2.ss, cur.ss) ) ;

		rec[i] = mk(p1,p2) ;

		if( (p2.ff-p1.ff+1)*(p2.ss-p1.ss+1) == i+1 )
		{
			if( !isRectangle[i] ) globalAns ++ ;
			isRectangle[i] = 1 ;
		}

		else
		{
			if( isRectangle[i] ) globalAns -- ;
			isRectangle[i] = 0 ;
		}

	}

	return globalAns ;

}


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] ) ;

	swap_seats( 0 , n-1 ) ;
	swap_seats(0,n-1) ;
}

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