제출 #212847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
212847		MarcoMeijer	자리 배치 (IOI18_seats)	C++14	37 / 100	4096 ms	137848 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());

template<class T, int DEF=0>
class Seg {
public:
	vi SEG;
	int sz;
	T t;

	void resize(int _sz) {
		sz = _sz;
		SEG.resize(sz*4);
	}
	void build(int p=0, int l=0, int r=-1) {
		if(r == -1) r = sz-1;
		if(l == r) {
			SEG[p] = 0;
			return;
		}
		int m=(l+r)/2;
		build(p*2+1,l,m);
		build(p*2+2,m+1,r);
		if(t(SEG[p*2+1], SEG[p*2+2])) 	SEG[p] = SEG[p*2+1];
		else							SEG[p] = SEG[p*2+2];
	}
	int get(int i, int j, int p=0, int l=0, int r=-1) {
		if(r == -1) r = sz-1;
		if(j < l || i > r) return DEF;
		if(i <= l && j >= r) return SEG[p];
		int m=(l+r)/2;
		int a=get(i,j,p*2+1,l,m);
		int b=get(i,j,p*2+2,m+1,r);
		if(t(a,b))	return a;
		else		return b;
	}
	void set(int i, int x, int p=0, int l=0, int r=-1) {
		if(r == -1) r = sz-1;
		if(i < l || i > r) return;
		if(l == r) {
			SEG[p] = x;
			return;
		}
		int m=(l+r)/2;
		set(i,x,p*2+1,l,m);
		set(i,x,p*2+2,m+1,r);
		if(t(SEG[p*2+1], SEG[p*2+2])) 	SEG[p] = SEG[p*2+1];
		else							SEG[p] = SEG[p*2+2];
	}
};

int h, w, n;
vi r, c;
vector<Seg<greater<int>>> maxR;
vector<Seg<greater<int>>> maxC;

int tot=0;
vi mnR, mxR, mnC, mxC;
vi added;

void updateRange(int L, int R) {
	REI(i,L,R) {
		if(added[i]) tot--;
		added[i] = 0;

		mnR[i] = r[i];
		mxR[i] = r[i];
		mnC[i] = c[i];
		mxC[i] = c[i];
		if(i != 0) {
			mnR[i] = min(mnR[i], mnR[i-1]);
			mxR[i] = max(mxR[i], mxR[i-1]);
			mnC[i] = min(mnC[i], mnC[i-1]);
			mxC[i] = max(mxC[i], mxC[i-1]);
		}
		if((mxR[i]-mnR[i]+1)*(mxC[i]-mnC[i]+1) == i+1) {
			tot++;
			added[i] = 1;
		}
	}
}
void give_initial_chart(int H, int W, vi R, vi C) {
	h=H, w=W, r=R, c=C;
	n = h*w;

	maxR.resize(h);
	maxC.resize(w);
	RE(i,h) maxR[i].resize(w);
	RE(i,w) maxC[i].resize(h);
	RE(i,n) maxR[r[i]].set(c[i],i);
	RE(i,n) maxC[c[i]].set(r[i],i);

	mnR  .assign(n,  INF);
	mxR  .assign(n, -INF);
	mnC  .assign(n,  INF);
	mxC  .assign(n, -INF);
	added.assign(n, 0);

	updateRange(0,n-1);
}

int swap_seats(int a, int b) {
	if(b < a) swap(a,b);
	swap(r[a], r[b]);
	swap(c[a], c[b]);

	if(h > 1000 || w > 1000) {
		updateRange(a,b);
		return tot;
	}

	maxR[r[a]].set(c[a],a);
	maxR[r[b]].set(c[b],b);
	maxC[c[a]].set(r[a],a);
	maxC[c[b]].set(r[b],b);

	int cnt	  = 0;
	int cMinR = r[0];
	int cMaxR = r[0];
	int cMinC = c[0];
	int cMaxC = c[0];
	int i 	  = 0;
	while(1) {
		if(i == (cMaxR-cMinR+1)*(cMaxC-cMinC+1)-1) cnt++;

		int val[4], res=0;
		val[0] = (cMinR == 0   ? INF : maxR[cMinR-1].get(cMinC, cMaxC));
		val[1] = (cMinC == 0   ? INF : maxC[cMinC-1].get(cMinR, cMaxR));
		val[2] = (cMaxR == h-1 ? INF : maxR[cMaxR+1].get(cMinC, cMaxC));
		val[3] = (cMaxC == w-1 ? INF : maxC[cMaxC+1].get(cMinR, cMaxR));
		RE(i,4) if(val[i] < val[res]) res = i;

		if(val[res] == INF) break;

		if(res == 0) cMinR--;
		if(res == 1) cMinC--;
		if(res == 2) cMaxR++;
		if(res == 3) cMaxC++;

		i = max(i, val[res]);
	}

	return cnt;
}

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