Submission #420227

#	Time	Username	Problem	Language	Result	Execution time	Memory
420227		Jasiekstrz	Seats (IOI18_seats)	C++17	17 / 100	4091 ms	56364 KiB

seats

#include<bits/stdc++.h>
#include "seats.h"
#define fi first
#define se second
using namespace std;
const int N=1e6;
int ans=0;
pair<int,int> tab[N+10];
int w[N+10][4];
bool is_ok(int x)
{
	return x==(w[x][1]-w[x][0]+1)*(w[x][3]-w[x][2]+1);
}
void upd(int x)
{
	w[x][0]=min(w[x-1][0],tab[x].fi);
	w[x][1]=max(w[x-1][1],tab[x].fi);
	w[x][2]=min(w[x-1][2],tab[x].se);
	w[x][3]=max(w[x-1][3],tab[x].se);
	return;
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C)
{
	int n=H*W;
	for(int i=1;i<=n;i++)
		tab[i]={R[i-1],C[i-1]};
	w[0][0]=H;
	w[0][1]=0;
	w[0][2]=W;
	w[0][3]=0;
	for(int i=1;i<=n;i++)
	{
		upd(i);
		ans+=is_ok(i);
	}
	return;
}
int swap_seats(int a,int b)
{
	a++;
	b++;
	if(a>b)
		swap(a,b);
	swap(tab[a],tab[b]);
	for(int i=a;i<b;i++)
	{
		ans-=is_ok(i);
		upd(i);
		ans+=is_ok(i);
	}
	return ans;
}

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