제출 #1275549

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

seats

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

using namespace std;

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

struct node
{
	int mxi, mni, mxj, mnj;
};


int n;
vector<int> R, C;
node sg[4*N];

void upd(int v, int l, int r, int i)
{
	if (l+1==r)
	{
		sg[v].mxi = sg[v].mni = R[i];
		sg[v].mxj = sg[v].mnj = C[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].mxi = max(sg[v*2+1].mxi, sg[v*2+2].mxi);
	sg[v].mni = min(sg[v*2+1].mni, sg[v*2+2].mni);
	sg[v].mxj = max(sg[v*2+1].mxj, sg[v*2+2].mxj);
	sg[v].mnj = min(sg[v*2+1].mnj, sg[v*2+2].mnj);
}

node qr(int v, int l, int r, int i, int j)
{
	if (l>=r || i >= r || j <= l)
		return {-inf, inf, -inf, inf};
	// cout << " " << l << " " << r << "\n";
	if (i <= l && j >= r)
	{
		// cout << sg[v].mnj << "\n";
		return sg[v];
	}
	int md = (l+r)/2;
	node lv = qr(v*2+1, l, md, i, j);
	node ds = qr(v*2+2, md, r, i, j);
	node tr = {max(lv.mxi, ds.mxi), min(lv.mni, ds.mni), max(lv.mxj, ds.mxj), min(lv.mnj, ds.mnj)};
	// cout << l << " " << r << " || " << tr.mxi << " " << tr.mni << " " << tr.mxj << " " << tr.mnj << "\n";
	return tr;
}

void give_initial_chart(int H, int W, std::vector<int> r, std::vector<int> c)
{
	R=r;C=c;
	n = H*W;
	for (int i = 0; i < n; i++)
		upd(0, 0, n, i);
}

int swap_seats(int a, int b)
{
	if (a>b)
		swap(a, b);
	swap(R[a], R[b]);
	swap(C[a], C[b]);
	upd(0, 0, n, a);
	upd(0, 0, n, b);
	int rez=0, tr=0;
	while (tr < n)
	{
		node zac = qr(0, 0, n, 0, tr+1);
		int dx = zac.mxi-zac.mni+1, dy = zac.mxj-zac.mnj+1;
		if (dx*dy==tr+1)
		{
			tr++;
			rez++;
		}
		else
			tr=dx*dy-1;
	}
	return rez;
}

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