Submission #294019

#	Time	Username	Problem	Language	Result	Execution time	Memory
294019		TheRedstar	Seats (IOI18_seats)	C++14	17 / 100	4046 ms	55672 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

int W,H;
vi R,C;

bitset<1000000> good;

int range[4][1000000];

int total=0;

int comp(int t, int a, int b) {
	if((t&1)==0) return min(a,b);
	return max(a,b);
}

void give_initial_chart(int h, int w, vi r, vi c) {
	W=w;
	H=h;
	R=r;
	C=c;
	

	for(int i=0; i<W*H; i++) {
		for(int j=0; j<4; j++) {
			if(i) range[j][i]=comp(j,range[j][i-1],j<2 ? R[i] : C[i]);
			else range[j][i]=j<2 ? R[i] : C[i];
		}
		if((range[1][i]-range[0][i]+1)*(range[3][i]-range[2][i]+1)==i+1) {
			good[i]=true;
			total++;
			//cout << "good " << i << endl;
		}
	}
	//cout << total << endl;
}

int swap_seats(int a, int b) {
	if(a>b) {a^=b;b^=a;a^=b;};
	int r1,c1,r2,c2;
	r1=R[a];
	c1=C[a];
	r2=R[b];
	c2=C[b];
	
	R[a]=r2;
	C[a]=c2;
	R[b]=r1;
	C[b]=c1;
	
	for(int i=a; i<=b; i++) {
		for(int j=0; j<4; j++) {
			if(i) range[j][i]=comp(j,range[j][i-1],j<2 ? R[i] : C[i]);
			else range[j][i]=j<2 ? R[i] : C[i];
		}
		
		if(((range[1][i]-range[0][i]+1)*(range[3][i]-range[2][i]+1)==i+1) ^ good[i]) {
			good[i]=good[i]^true;
			total=total-1+2*good[i];
			//cout << "changed " << i << endl;
		}
	}
	
	return total;
}

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