Submission #379312

#	Time	Username	Problem	Language	Result	Execution time	Memory
379312		autumn_eel	Seats (IOI18_seats)	C++14	11 / 100	4077 ms	43756 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;

static int h,w;
static vector<int>r,c;
static vector<int>ok;
static vector<int>rmin,rmax,cmin,cmax;
static int sum;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	h=H;w=W;
	r=R;c=C;
	ok=vector<int>(h*w);
	rmin=rmax=cmin=cmax=vector<int>(h*w);
	rep(i,h*w){
		rmin[i]=rmax[i]=r[i];
		cmin[i]=cmax[i]=c[i];
		if(i){
			rmin[i]=min(rmin[i-1],rmin[i]);
			rmax[i]=max(rmax[i-1],rmax[i]);
			cmin[i]=min(cmin[i-1],cmin[i]);
			cmax[i]=max(cmax[i-1],cmax[i]);
		}
		if((rmax[i]-rmin[i]+1)*(cmax[i]-cmin[i]+1)==i+1){
			sum++;
			ok[i]=1;
		}
	}
}

int swap_seats(int a, int b) {
	swap(r[a],r[b]);
	swap(c[a],c[b]);
	for(int i=0;i<=h*w-1;i++){
		rmin[i]=rmax[i]=r[i];
		cmin[i]=cmax[i]=c[i];
		if(i){
			rmin[i]=min(rmin[i-1],rmin[i]);
			rmax[i]=max(rmax[i-1],rmax[i]);
			cmin[i]=min(cmin[i-1],cmin[i]);
			cmax[i]=max(cmax[i-1],cmax[i]);
		}
		sum-=ok[i];
		if((rmax[i]-rmin[i]+1)*(cmax[i]-cmin[i]+1)==i+1){
			sum++;
			ok[i]=1;
		}
		else ok[i]=0;
	}
	return sum;
}

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