Submission #299652

#	Time	Username	Problem	Language	Result	Execution time	Memory
299652		TMJN	Seats (IOI18_seats)	C++17	17 / 100	4066 ms	42212 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

int H,W,res;
vector<pair<int,int>>XY;
vector<int>Xmin,Xmax,Ymin,Ymax;

void give_initial_chart(int h,int w,vector<int>R,vector<int>C){
	H=h;
	W=w;
	Xmin=Ymin=Xmax=Ymax=vector<int>(H*W);
	for(int i=0;i<H*W;i++){
		XY.push_back({R[i],C[i]});
	}
	Xmin[0]=Xmax[0]=XY[0].first;
	Ymin[0]=Ymax[0]=XY[0].second;
	for(int i=1;i<H*W;i++){
		Xmin[i]=min(Xmin[i-1],XY[i].first);
		Xmax[i]=max(Xmax[i-1],XY[i].first);
		Ymin[i]=min(Ymin[i-1],XY[i].second);
		Ymax[i]=max(Ymax[i-1],XY[i].second);
	}
	for(int i=0;i<H*W;i++){
		if(i+1==(Xmax[i]-Xmin[i]+1)*(Ymax[i]-Ymin[i]+1)){
			res++;
		}
	}
}

int swap_seats(int a,int b){
	if(a>b)swap(a,b);
	swap(XY[a],XY[b]);
	if(!a){
		Xmin[0]=Xmax[0]=XY[0].first;
		Ymin[0]=Ymax[0]=XY[0].second;
	}
	for(int i=max(a,1);i<=b;i++){
		if(i+1==(Xmax[i]-Xmin[i]+1)*(Ymax[i]-Ymin[i]+1)){
			res--;
		}
		Xmin[i]=min(Xmin[i-1],XY[i].first);
		Xmax[i]=max(Xmax[i-1],XY[i].first);
		Ymin[i]=min(Ymin[i-1],XY[i].second);
		Ymax[i]=max(Ymax[i-1],XY[i].second);
		if(i+1==(Xmax[i]-Xmin[i]+1)*(Ymax[i]-Ymin[i]+1)){
			res++;
		}
	}
	return res;
}

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