Submission #218671

#	Time	Username	Problem	Language	Result	Execution time	Memory
218671		MarcoMeijer	Seats (IOI18_seats)	C++14	0 / 100	4074 ms	77068 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());
 
int h, w, n;
vi r, c;
vector<vi> A;
int dx[]={-1, 0, 1, 0};
int dy[]={ 0,-1, 0, 1};

vi SEG, SEGMIN, SEGCNT;
 
void updateNode(int p) {
	SEG[p] = 0;
	SEGMIN[p] = min(SEGMIN[p*2+1], SEGMIN[p*2+2]);
	SEGCNT[p] = 0;
	if(SEGMIN[p*2+1] == SEGMIN[p]) SEGCNT[p] += SEGCNT[p*2+1];
	if(SEGMIN[p*2+2] == SEGMIN[p]) SEGCNT[p] += SEGCNT[p*2+2];
}
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;
	buildSeg(p*2+1,L,m);
	buildSeg(p*2+2,m+1,R);
	updateNode(p);
}
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;
	addSeg(i,j,x,SEG[p],p*2+1,L,m);
	addSeg(i,j,x,SEG[p],p*2+2,m+1,R);
	updateNode(p);
}
int getEnd(ii pos) {
	if(pos.fi < 0 || pos.fi >= h) return n-1;
	if(pos.se < 0 || 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) return;
	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);
}

void give_initial_chart(int H, int W, vi R, vi C) {
	h=H, w=W, r=R, c=C;
	n = h*w;
	SEG   .resize(n*4);
	SEGMIN.resize(n*4);
	SEGCNT.resize(n*4);
	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});
		RE(i,4) {
			ii cent = {r[a]+dx[i],c[a]+dy[i]};
			RE(j,4) updated.insert({cent, j});
		}
	}
	// b's neighbours
	{
		RE(i,4) updated.insert({{r[b],c[b]}, i});
		RE(i,4) {
			ii cent = {r[b]+dx[i],c[b]+dy[i]};
			RE(j,4) updated.insert({cent, j});
		}
	}

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