Submission #368041

#	Time	Username	Problem	Language	Result	Execution time	Memory
368041		dennisstar	Seats (IOI18_seats)	C++17	0 / 100	1014 ms	84076 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;

struct {
	int st[1<<20], ss[1<<20];
	void upd(int t, int v) {
		t++;
		v-=ss[t];
		ss[t]+=v;
		while (t<=H*W) st[t]+=v, t+=t&-t;
	}
	int get(int t) {
		t++;
		int r=0;
		while (t) r+=st[t], t-=t&-t;
		return r;
	}
}fc, fd;

pii st[1<<21];
int ss[1<<21];
void upd(int i, int s, int e, int t, pii p) {
	if (s==e) {
		st[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);
	tie(st[i], ss[i])=min(tie(st[i*2], ss[i*2]), tie(st[i*2+1], ss[i*2+1]));
	if (st[i*2]==st[i*2+1]) 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--;
	}
	fc.upd(S[x][y], c);
	fd.upd(S[x][y], d);
	upd(1, 0, H*W-1, S[x][y], pii(fc.get(S[x][y]), fd.get(S[x][y])));
}

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: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30