Submission #434148

#	Time	Username	Problem	Language	Result	Execution time	Memory
434148		vanic	Seats (IOI18_seats)	C++14	0 / 100	4069 ms	39480 KiB

seats

#include "seats.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <array>

using namespace std;

const int maxn=1e6+5;

vector < int > r;
vector < int > c;
bool dobar[maxn];
int sol;
array < int, 4 > v[maxn];
int n, m;

void give_initial_chart(int H, int W, vector < int > R, vector < int > C) {
	r=R;
	c=C;
	n=H;
	m=W;
	int maxx=0, maxy=0, minx=1e9, miny=1e9;
	for(int i=0; i<n*m; i++){
		maxx=max(maxx, r[i]);
		maxy=max(maxy, c[i]);
		minx=min(minx, r[i]);
		miny=min(miny, c[i]);
		if((maxx-minx+1)*(maxy-miny+1)==i+1){
			sol++;
			dobar[i]=1;
		}
		v[i]={minx, miny, maxx, maxy};
	}
}

int swap_seats(int a, int b) {
	array < int, 4 > prosl;
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	for(int i=a; i<b; i++){
		if(i){
			prosl=v[i-1];
		}
		else{
			prosl={(int)1e9, (int)1e9, 0, 0};
		}
		v[i][0]=min(prosl[0], r[i]);
		v[i][1]=min(prosl[1], c[i]);
		v[i][2]=max(prosl[2], r[i]);
		v[i][3]=max(prosl[3], c[i]);
		if((v[i][2]-v[i][0]+1)*(v[i][3]-v[i][1]+1)==i+1){
			if(!dobar[i]){
				dobar[i]=1;
				sol++;
			}
		}
		else{
			if(dobar[i]){
				dobar[i]=0;
				sol--;
			}
		}
	}
	return sol;
}

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