Submission #368046

#	Time	Username	Problem	Language	Result	Execution time	Memory
368046		dennisstar	Seats (IOI18_seats)	C++17	100 / 100	1689 ms	135804 KiB

seats

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

using namespace std;
using pii = pair<int, int>;

const int xx[] = {0, -1, -1, -1, 0, 1, 1, 1, 0};
const int yy[] = {-1, -1, 0, 1, 1, 1, 0, -1, -1};

int H, W;
vector<int> R, C;
vector<vector<int>> S;

pii s1[1<<21], s2[1<<21];
int ss[1<<21];
void upd(int i, int s, int e, int t, pii p) {
	if (s==e) {
		s1[i]=s2[i]=p;
		ss[i]=1;
		return ;
	}

	int m=(s+e)/2;
	if (t<=m) upd(i*2, s, m, t, p);
	else upd(i*2+1, m+1, e, t, p);

	s1[i]=pii(s1[i*2].first+s1[i*2+1].first, s1[i*2].second+s1[i*2+1].second);
	pii pp(s1[i*2].first+s2[i*2+1].first, s1[i*2].second+s2[i*2+1].second);
	tie(s2[i], ss[i])=min(tie(s2[i*2], ss[i*2]), tie(pp, ss[i*2+1]));
	if (s2[i*2]==pp) ss[i]+=max(ss[i*2], ss[i*2+1]);
}

bool av(int x, int y) { return 0<=x&&x<=H-1&&0<=y&&y<=W-1; }

void upd(int x, int y) {
	int c=0, d=0;
	for (int i=1; i<=7; i+=2) {
		int cc=0;
		for (int j=-1; j<=1; j++)
			if (av(x+xx[i+j], y+yy[i+j])
				&&S[x+xx[i+j]][y+yy[i+j]]<S[x][y]) cc++;
		if (cc==0) c++;
		if (cc==1) {
			if (av(x+xx[i], y+yy[i])
				&&S[x+xx[i]][y+yy[i]]<S[x][y]) c++;
			else c--;
		}
		if (cc==2) {
			if (S[x+xx[i]][y+yy[i]]>S[x][y]) c-=2;
			d++;
		}
		if (cc==3) d--;
	}
	upd(1, 0, H*W-1, S[x][y], pii(c, d));
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	::H=H;
	::W=W;
	::R=R;
	::C=C;
	S.resize(H, vector<int>(W, 1e9));
	for (int i=0; i<H*W; i++) {
		S[R[i]][C[i]]=i;
		upd(R[i], C[i]);
	}
}

int swap_seats(int a, int b) {
	swap(R[a], R[b]);
	swap(C[a], C[b]);
	swap(S[R[a]][C[a]], S[R[b]][C[b]]);

	vector<pii> U;
	U.emplace_back(R[a], C[a]);
	U.emplace_back(R[b], C[b]);
	for (int i=0; i<=7; i++) {
		if (av(R[a]+xx[i], C[a]+yy[i])) U.emplace_back(R[a]+xx[i], C[a]+yy[i]);
		if (av(R[b]+xx[i], C[b]+yy[i])) U.emplace_back(R[b]+xx[i], C[b]+yy[i]);
	}
	sort(U.begin(), U.end(), [&](pii &p1, pii &p2) {
		return S[p1.first][p1.second]<S[p2.first][p2.second];
	});
	U.resize(unique(U.begin(), U.end())-U.begin());

	for (auto &i:U) upd(i.first, i.second);
	return ss[1];
}

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