제출 #831528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831528		caganyanmaz	자리 배치 (IOI18_seats)	C++17	5 / 100	4077 ms	55904 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
using namespace std;

constexpr static int MXN = 1e6;
constexpr static int INF = 1e6;
constexpr static int MXST = MXN<<1;
//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

struct SegTree
{
	int def;
	function<int(int, int)> merge;
	int n;
	int v[MXST];
	void build(int n, vector<int>& a, function<int(int, int)> merge, int def)
	{
		this->n = n;
		this->merge = merge;
		this->def = def;
		for (int i = n; i < 2*n; i++) v[i] = a[i-n];
		for (int i = n-1; i > 0; i--) v[i] = merge(v[i<<1], v[(i<<1)|1]);
	}
	void set(int i, int val) { for (v[i+=n]=val;i>1;i>>=1) v[i>>1] = merge(v[i], v[i^1]); }
	int get(int l, int r)
	{
		int res = def;
		l = max(l, 0);
		r = min(r, n);
		for (l+=n,r+=n;r>l;r>>=1,l>>=1)
		{
			if (l&1) res = merge(res, v[l++]);
			if (r&1) res = merge(res, v[--r]);
		}
		return res;
	}

};

vector<int> r, c;
SegTree mnr, mxr, mnc, mxc;

int h, w, n;
int counter;
set<int> rects;
int mn(int a, int b) {return min(a,b);}
int mx(int a, int b) {return max(a,b);}

bool is_rect(int i)
{
	int rect_size = (mxr.get(0, i+1) - mnr.get(0, i+1) + 1) * (mxc.get(0, i+1) - mnc.get(0, i+1) + 1);
	return rect_size == i+1;
}

void create_table()
{
	counter = 0;
	mnr.build(n, r, mn, INF);
	mxr.build(n, r, mx, -INF);
	mnc.build(n, c, mn, INF);
	mxc.build(n, c, mx, -INF);
	for (int i = 0; i < n; i++)
		if (is_rect(i))
			rects.insert(i);
	debug(rects);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) 
{
	r = R, c = C;
	h = H, w = W;
	n = h*w;
	set<int> rects;
	create_table();
}

int swap_seats(int a, int b)
{
	if (a > b)
		swap(a, b);
	for (int i= 0; i < 2; i++)
	{
		mnr.set(a, r[b]);
		mxr.set(a, r[b]);
		mnc.set(a, c[b]);
		mxc.set(a, c[b]);
		swap(a, b);
	}
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	for (int i = a; i <= b; i++)
	{
		bool res = is_rect(i);
		if (!res)
			rects.erase(i);
		if (res)
			rects.insert(i);
	}
	return rects.size();
}

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