제출 #1276378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276378		raspy	자리 배치 (IOI18_seats)	C++20	0 / 100	165 ms	70824 KiB

seats

#include "seats.h"
#include <iostream>

using namespace std;

const int N = 1e6+10;
const int inf = 1e9;

struct node
{
	int mn;
	int st_mn;
	int prsm;
	node() : mn(2), st_mn(1), prsm(0) { }
};

int n = 0;
node sg[4*N];
int lz[4*N];
int pr2[4*N];
int delta[4*N];
int poz[N];
int vre[N];

node create(int vr)
{
	node rez;
	rez.mn = rez.prsm = vr;
	rez.st_mn=1;
	return rez;
}

node join(node l, node r)
{
	node rez;
	if (l.mn == r.mn+l.prsm)
	{
		rez.mn = l.mn;
		rez.st_mn = l.st_mn+r.st_mn;
		rez.prsm = l.prsm+r.prsm;
	}
	else if (l.mn < r.mn+l.prsm)
	{
		rez.mn = l.mn;
		rez.st_mn = l.st_mn;
		rez.prsm = l.prsm+r.prsm;
	}
	else
	{
		rez.mn = r.mn+l.prsm;
		rez.st_mn = r.st_mn;
		rez.prsm = r.prsm+r.prsm;
	}
	return rez;
}

void build(int v, int l, int r)
{
	if (l+1==r)
	{
		sg[v] = create(delta[l]);
		return;
	}
	int md = (l+r)/2;
	build(v*2+1, l, md);
	build(v*2+2, md, r);
	sg[v] = join(sg[v*2+1], sg[v*2+2]);
}

void upd(int v, int l, int r, int i)
{
	if (l+1 == r)
	{
		sg[v] = create(delta[i]);
		return;
	}
	int md = (l+r)/2;
	if (i < md)
		upd(v*2+1, l, md, i);
	else
		upd(v*2+2, md, r, i);
	sg[v] = join(sg[v*2+1], sg[v*2+2]);
}

int calc_delta(int vr)
{
	int ix = poz[vr];
	int dl = 0;
	dl += ((ix==0 || vre[ix-1]>vr) ? 1 : -1);
	dl += ((ix==n-1 || vre[ix+1]>vr) ? 1 : -1);
	return dl;
}

void upd_delta(int ix)
{
	if (ix<0||ix>=n)
		return;
	int vr = vre[ix];
	delta[vr] = calc_delta(vr);
	upd(0, 0, n, vr);
}

void give_initial_chart(int H, int W, std::vector<int> r, std::vector<int> c)
{
	n=H*W;
	for (int i = 0; i < n; i++)
	{
		poz[i] = c[i];
		vre[poz[i]]=i;
	}
	for (int i = 0; i < n; i++)
		delta[i] = calc_delta(i);
	build(0, 0, n);
}

int swap_seats(int a, int b)
{
	swap(vre[poz[a]], vre[poz[b]]);
	swap(poz[a], poz[b]);
	upd_delta(poz[a]-1); upd_delta(poz[b]-1);
	upd_delta(poz[a]); upd_delta(poz[b]);
	upd_delta(poz[a]+1); upd_delta(poz[b]+1);
	return sg[0].st_mn;
}

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