Submission #76494

#	Time	Username	Problem	Language	Result	Execution time	Memory
76494		Xellos	Seats (IOI18_seats)	C++14	11 / 100	4053 ms	134140 KiB

seats

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

int R, C;
vector< vector<int> > table;
vector<int> pos_R, pos_C;
vector< set<int> > row_lst;
vector<int> rowmin_top, rowmin_bot;
vector<int> sdiv;
vector< vector<int> > group_min, group_max;
vector<int> group1000_min, group1000_max;

void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
	if(H > W) {
		swap(H, W);
		swap(r, c);
	}
	R = H;
	C = W;
	pos_R = r, pos_C = c;
	table.resize(R, vector<int>(C));
	for(int i = 0; i < H*W; i++) table[r[i]][c[i]] = i;
	row_lst.resize(R);
	for(int i = 0; i < H*W; i++) row_lst[r[i]].insert(i);
	rowmin_top.resize(R+1, R*C);
	rowmin_bot.resize(R+1, R*C);
	sdiv.resize(R, 0);
	for(int i = 0; i < R; i++)
		for(int j = 2; j*j <= i+1; j++) if((i+1)%j == 0) sdiv[i] = j-1;
	group_min.resize(R);
	group_max.resize(R);
	for(int i = 0; i < R; i++) {
		group_min[i].resize(R*C/(i+1), C);
		group_max[i].resize(R*C/(i+1), 0);
		for(int j = 0; j < R*C/(i+1); j++) {
			if(sdiv[i]) for(int k = 0; k < (i+1)/(sdiv[i]+1); k++) {
				group_min[i][j] = min(group_min[i][j], group_min[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
				group_max[i][j] = max(group_max[i][j], group_max[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
			}
			else if(i < 15) for(int k = 0; k < i+1; k++) {
				group_min[i][j] = min(group_min[i][j], pos_C[j*(i+1)+k]);
				group_max[i][j] = max(group_max[i][j], pos_C[j*(i+1)+k]);
			}
			else {
				int cur = j*(i+1);
				while(cur%13 != 0) {
					group_min[i][j] = min(group_min[i][j], pos_C[cur]);
					group_max[i][j] = max(group_max[i][j], pos_C[cur]);
					cur++;
				}
				while(cur+13 <= (j+1)*(i+1)) {
					group_min[i][j] = min(group_min[i][j], group_min[12][cur/13]);
					group_max[i][j] = max(group_max[i][j], group_max[12][cur/13]);
					cur += 13;
				}
				while(cur < (j+1)*(i+1)) {
					group_min[i][j] = min(group_min[i][j], pos_C[cur]);
					group_max[i][j] = max(group_max[i][j], pos_C[cur]);
					cur++;
				}
			}
		}
	}
	group1000_min.resize(R*C/1000, C);
	group1000_max.resize(R*C/1000, 0);
	for(int i = 0; i < R*C/1000; i++) for(int j = 0; j < 1000; j++) {
		group1000_min[i] = min(group1000_min[i], pos_C[i*1000+j]);
		group1000_max[i] = max(group1000_max[i], pos_C[i*1000+j]);
	}
}

int swap_seats(int a, int b) {
	// if(C > 10000) return 0;
	row_lst[pos_R[a]].erase(a);
	row_lst[pos_R[b]].erase(b);
	swap(table[pos_R[a]][pos_C[a]], table[pos_R[b]][pos_C[b]]);
	swap(pos_R[a], pos_R[b]);
	swap(pos_C[a], pos_C[b]);
	row_lst[pos_R[a]].insert(a);
	row_lst[pos_R[b]].insert(b);
	for(int i = 0; i < R; i++) if(a/(i+1) < R*C/(i+1)) {
		group_min[i][a/(i+1)] = C;
		group_max[i][a/(i+1)] = 0;
		int j = a/(i+1);
		if(sdiv[i]) for(int k = 0; k < (i+1)/(sdiv[i]+1); k++) {
			group_min[i][j] = min(group_min[i][j], group_min[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
			group_max[i][j] = max(group_max[i][j], group_max[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
		}
		else if(i < 15) for(int k = 0; k < i+1; k++) {
			group_min[i][j] = min(group_min[i][j], pos_C[j*(i+1)+k]);
			group_max[i][j] = max(group_max[i][j], pos_C[j*(i+1)+k]);
		}
		else {
			int cur = j*(i+1);
			while(cur%13 != 0) {
				group_min[i][j] = min(group_min[i][j], pos_C[cur]);
				group_max[i][j] = max(group_max[i][j], pos_C[cur]);
				cur++;
			}
			while(cur+13 <= (j+1)*(i+1)) {
				group_min[i][j] = min(group_min[i][j], group_min[12][cur/13]);
				group_max[i][j] = max(group_max[i][j], group_max[12][cur/13]);
				cur += 13;
			}
			while(cur < (j+1)*(i+1)) {
				group_min[i][j] = min(group_min[i][j], pos_C[cur]);
				group_max[i][j] = max(group_max[i][j], pos_C[cur]);
				cur++;
			}
		}
	}
	for(int i = 0; i < R; i++) if(b/(i+1) < R*C/(i+1)) {
		group_min[i][b/(i+1)] = C;
		group_max[i][b/(i+1)] = 0;
		int j = b/(i+1);
		if(sdiv[i]) for(int k = 0; k < (i+1)/(sdiv[i]+1); k++) {
			group_min[i][j] = min(group_min[i][j], group_min[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
			group_max[i][j] = max(group_max[i][j], group_max[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
		}
		else if(i < 15) for(int k = 0; k < i+1; k++) {
			group_min[i][j] = min(group_min[i][j], pos_C[j*(i+1)+k]);
			group_max[i][j] = max(group_max[i][j], pos_C[j*(i+1)+k]);
		}
		else {
			int cur = j*(i+1);
			while(cur%13 != 0) {
				group_min[i][j] = min(group_min[i][j], pos_C[cur]);
				group_max[i][j] = max(group_max[i][j], pos_C[cur]);
				cur++;
			}
			while(cur+13 <= (j+1)*(i+1)) {
				group_min[i][j] = min(group_min[i][j], group_min[12][cur/13]);
				group_max[i][j] = max(group_max[i][j], group_max[12][cur/13]);
				cur += 13;
			}
			while(cur < (j+1)*(i+1)) {
				group_min[i][j] = min(group_min[i][j], pos_C[cur]);
				group_max[i][j] = max(group_max[i][j], pos_C[cur]);
				cur++;
			}
		}
	}
	if(a/1000 < R*C/1000) {
		group1000_min[a/1000] = C;
		group1000_max[a/1000] = 0;
		for(int j = 0; j < 1000; j++) {
			group1000_min[a/1000] = min(group1000_min[a/1000], pos_C[(a/1000)*1000+j]);
			group1000_max[a/1000] = max(group1000_max[a/1000], pos_C[(a/1000)*1000+j]);
		}
	}
	if(b/1000 < R*C/1000) {
		group1000_min[b/1000] = C;
		group1000_max[b/1000] = 0;
		for(int j = 0; j < 1000; j++) {
			group1000_min[b/1000] = min(group1000_min[b/1000], pos_C[(b/1000)*1000+j]);
			group1000_max[b/1000] = max(group1000_max[b/1000], pos_C[(b/1000)*1000+j]);
		}
	}
	int ans = 0, cur_max = 0;
	int rl = pos_R[0], rr = pos_R[0], cl = pos_C[0], cr = pos_C[0];
	for(int i = 0; i < pos_R[0]; i++) rowmin_top[i+1] = min(rowmin_top[i], *begin(row_lst[i]));
	for(int i = R-1; i >= pos_R[0]; i--) rowmin_bot[i] = min(rowmin_bot[i+1], *begin(row_lst[i]));
	for(int i = 0; i < R; i++) {
		int cur_out_min = min(rowmin_bot[rr+1], rowmin_top[rl]);
		int D = cur_max / (rr-rl+1);
		cl = min(cl, group_min[rr-rl][D]);
		cr = max(cr, group_max[rr-rl][D]);
		cur_max = (D+1) * (rr-rl+1) - 1;
		while((rr-rl+1)*(cr-cl+1) <= cur_out_min) {
			if((rr-rl+1)*(cr-cl+1) == cur_max+1) ans++;
			D++;
			if(cur_max+rr-rl+1 >= cur_out_min) break;
			cur_max += rr-rl+1;
			if(D < R*C/(rr-rl+1)) {
				cl = min(cl, group_min[rr-rl][D]);
				cr = max(cr, group_max[rr-rl][D]);
			}
		}
		if(i == R-1) break;
		int min_top = (rl == 0)   ? R*C : *begin(row_lst[rl-1]);
		int min_bot = (rr == R-1) ? R*C : *begin(row_lst[rr+1]);
		if(min_top < min_bot) rl--;
		else rr++;
	}
	return ans;
}

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