Submission #138278

#	Time	Username	Problem	Language	Result	Execution time	Memory
138278		Lawliet	Seats (IOI18_seats)	C++14	17 / 100	4099 ms	67576 KiB

seats

#include <bits/stdc++.h>

#define MAX 1000010
#define INF 1000000000

using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;
typedef pair<pii,pii> rectangle;

int N, M;
int curAns;

bool can[MAX];

pii pos[MAX];

rectangle lim[MAX];

vector<int> v[MAX];

void update(int l, int r)
{
	for(int g = l ; g <= r ; g++)
	{
		int& mxX = lim[g].first.first;
		int& mnX = lim[g].first.second;
		int& mxY = lim[g].second.first;
		int& mnY = lim[g].second.second;

		mxX = max(pos[g].first , lim[g - 1].first.first);
		mnX = min(pos[g].first , lim[g - 1].first.second);
		mxY = max(pos[g].second , lim[g - 1].second.first);
		mnY = min(pos[g].second , lim[g - 1].second.second);

		//printf("-> %d ============ %d %d %d %d\n",g,mxX,mnX,mxY,mnY);

		if((mxX - mnX + 1)*(mxY - mnY + 1) == g)
			curAns++, can[g] = true;
	}
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
	N = H; M = W;

	for(int g = 1 ; g <= N*M ; g++)
		pos[g] = {R[g - 1] , C[g - 1]};

	lim[0] = {{-INF , INF} , {-INF , INF}};

	update(1 , N*M);

	//printf("-> %d\n",curAns);
}



int swap_seats(int a, int b)
{
  	if(a > b) swap(a , b);
	a++; b++;

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

	for(int g = a ; g <= b ; g++)
	{
		if(can[g]) curAns--;
		can[g] = false;
	}

	update(a , b);

	//printf(" -> %d %d\n",pos[0].first,pos[0].second);

	return curAns;
}

/*int main()
{
	int nn, mm, qq;
	scanf("%d %d %d",&nn,&mm,&qq);

	vector<int> rr(nn*mm), cc(nn*mm);

	for(int g = 0 ; g < nn*mm ; g++)
		scanf("%d %d",&rr[g],&cc[g]);

	give_initial_chart(nn , mm , rr , cc);

	for(int g = 0 ; g < qq ; g++)
	{
		int n1, n2;
		scanf("%d %d",&n1,&n2);

		printf("%d",swap_seats(n1 , n2));
	}
}*/

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