Submission #218692

#	Time	Username	Problem	Language	Result	Execution time	Memory
218692		MarcoMeijer	Seats (IOI18_seats)	C++14	100 / 100	3125 ms	105216 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
 
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MX=1e6+1e5;

int h, w, n;
vi r, c;
vector<vi> A;
int dx[]={-1, 0, 1, 0};
int dy[]={ 0,-1, 0, 1};

int SEG[MX*4], SEGMIN[MX*4], SEGCNT[MX*4];
 
inline void updateNode(int p, int lp, int rp) {
	SEG   [p] = 0;
	SEGMIN[p] = min(SEGMIN[lp], SEGMIN[rp]);
	SEGCNT[p] = 0;
	if(SEGMIN[lp] == SEGMIN[p]) SEGCNT[p] += SEGCNT[lp];
	if(SEGMIN[rp] == SEGMIN[p]) SEGCNT[p] += SEGCNT[rp];
}
void buildSeg(int p=0, int L=0, int R=n-1) {
	if(L == R) {
		SEG[p] = 0;
		SEGMIN[p] = 0;
		SEGCNT[p] = 1;
		return;
	}
	int m=(L+R)/2;
	int lp=p*2+1;
	int rp=p*2+2;
	buildSeg(lp,L,m);
	buildSeg(rp,m+1,R);
	updateNode(p,lp,rp);
}
void addSeg(int i, int j, int x, int lazy=0, int p=0, int L=0, int R=n-1) {
	SEG   [p] += lazy;
	SEGMIN[p] += lazy;
	if(j < L || i > R) return;
	if(i <= L && j >= R) {
		SEG   [p] += x; 
		SEGMIN[p] += x; 
		return;
	}
	int m=(L+R)/2;
	int lp=p*2+1;
	int rp=p*2+2;
	addSeg(i,j,x,SEG[p],lp,L,m);
	addSeg(i,j,x,SEG[p],rp,m+1,R);
	updateNode(p,lp,rp);
}
int getEnd(ii pos) {
	if(pos.fi == -1 || pos.fi == h) return n-1;
	if(pos.se == -1 || pos.se == w) return n-1;
	return A[pos.fi][pos.se]-1;
}
void updateNeigbours(ii cent, ii pos1, ii pos2, int x=1) {
	if(getEnd(cent) == n-1) return;
	int bg = A[cent.fi][cent.se];
	int ed = min(getEnd(pos1), getEnd(pos2));
	if(ed >= bg) addSeg(bg, ed, x);
}
void updateNeigbours2(ii cent, ii pos1, ii pos2, int x=1) {
	if(getEnd(cent) == n-1) return;
	int bg = max(getEnd(pos1), getEnd(pos2))+1;
	int ed = A[cent.fi][cent.se]-1;
	if(ed >= bg) addSeg(bg, ed, x);
}
void updateNeigbours(ii cent, int d, int x=1) {
	int d1 = d;
	int d2 = (d+1)%4;
	ii pos1 = {cent.fi+dx[d1], cent.se+dy[d1]};
	ii pos2 = {cent.fi+dx[d2], cent.se+dy[d2]};
	updateNeigbours(cent, pos1, pos2, x);
	if(d == 0) updateNeigbours2(cent, pos1, pos2, x);
}

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

	A.resize(h);
	RE(i,h) A[i].resize(w);
	RE(i,n) A[r[i]][c[i]] = i;

	buildSeg();
	RE(i,h) RE(j,w) RE(k,4) updateNeigbours({i,j}, k);
}

int swap_seats(int a, int b) {
	set<pair<ii, int>> updated;

	// a's neighbours
	RE(i,4) updated.insert({{r[a],c[a]}, i});
	updated.insert({{r[a]+1,c[a]  }, 0});
	updated.insert({{r[a]-1,c[a]  }, 1});
	updated.insert({{r[a]-1,c[a]  }, 2});
	updated.insert({{r[a]+1,c[a]  }, 3});
	updated.insert({{r[a]  ,c[a]+1}, 0});
	updated.insert({{r[a]  ,c[a]+1}, 1});
	updated.insert({{r[a]  ,c[a]-1}, 2});
	updated.insert({{r[a]  ,c[a]-1}, 3});

	// b's neighbours
	RE(i,4) updated.insert({{r[b],c[b]}, i});
	updated.insert({{r[b]+1,c[b]  }, 0});
	updated.insert({{r[b]-1,c[b]  }, 1});
	updated.insert({{r[b]-1,c[b]  }, 2});
	updated.insert({{r[b]+1,c[b]  }, 3});
	updated.insert({{r[b]  ,c[b]+1}, 0});
	updated.insert({{r[b]  ,c[b]+1}, 1});
	updated.insert({{r[b]  ,c[b]-1}, 2});
	updated.insert({{r[b]  ,c[b]-1}, 3});

	for(auto p : updated) updateNeigbours(p.fi, p.se, -1);

	swap(r[a], r[b]);
	swap(c[a], c[b]);
	A[r[a]][c[a]] = a;
	A[r[b]][c[b]] = b;

	for(auto p : updated) updateNeigbours(p.fi, p.se, 1);

	if(SEGMIN[0] != 4) return 0;
	else return SEGCNT[0]; 
}

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