제출 #294110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
294110		amoo_safar	자리 배치 (IOI18_seats)	C++17	0 / 100	4030 ms	57464 KiB

seats

#include "seats.h"

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 1e6 + 10;

vi R, C;
int H, W;
vector<vi> A;

int GetMin(int l1, int r1, int l2, int r2){
	int mn = H*W;
	for(int i = l1; i < r1; i ++)
		for(int j = l2; j < r2; j++)
			mn = min(mn, A[i][j]);
	return mn;
}

pii BadRange(int i, int j){
	vector<pii> V;
	V.pb({GetMin(0, i + 1, 0, j + 1), 0});
	V.pb({GetMin(0, i + 1, j, W), 1});
	V.pb({GetMin(i, H, 0, j + 1), 2});
	V.pb({GetMin(i, H, j, W), 3});
	sort(all(V));
	if(3 - V[0].S == V[1].S) return {V[1].F, A[i][j]};
	return {V[2].F, A[i][j]};
}

pii seg[N << 2];
int lz[N << 2];
void Apply(int id, int x){
	lz[id] += x;
	seg[id].F += x;
}
void Shift(int id){
	Apply(id << 1, lz[id]);
	Apply(id << 1 | 1, lz[id]);
	lz[id] = 0;
}
void Build(int id = 1, int L = 0, int R = H * W){
	seg[id] = {0, R - L};
	lz[id] = 0;
	if(L + 1 == R) return ;
	int mid = (L + R) >> 1;
	Build(id << 1, L, mid);
	Build(id << 1 | 1, mid, R);
}
pii Merge(pii &A, pii &B){
	if(A.F != B.F) return min(A, B);
	return {A.F, A.S + B.S};
}
int Val[N];
void Add(int id, int l, int r, int x, int L = 0, int R = H * W){
	for(int i = l; i < r; i++) Val[i] += x;
	return ;
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		Apply(id, x);
		return ;
	}
	Shift(id);
	int mid = (L + R) >> 1;
	Add(id << 1, l, r, x, L, mid);
	Add(id << 1 | 1, l, r, x, mid, R);
	seg[id] = Merge(seg[id << 1], seg[id << 1 | 1]);
	return ;
}
int Get0(){
	int res = 0;
	for(int i = 0; i < H*W; i++)
		if(Val[i] == 0)
			res ++;
	return res;
}
void AddCell(int i, int j, int z){
	pii ran = BadRange(i, j);
	//cerr << "! " << i << ' ' << j << " " << ran.F << '\n';
	if(ran.F < ran.S)
		Add(1, ran.F, ran.S, z);
}

void give_initial_chart(int _H, int _W, vi _R, vi _C){
	R = _R; C = _C;
	H = _H; W = _W;

	A.resize(H, vector<int> (W, 0));
	for(int i = 0; i < H * W; i++)
		A[R[i]][C[i]] = i;
	Build();
	for(int i = 0; i < H; i++)
		for(int j = 0; j < W; j++)
			AddCell(i, j, +1);
	//cerr << seg[1].S << ' ' << "#########\n";
}

int swap_seats(int a, int b){
	AddCell(R[a], C[a], -1);
	AddCell(R[b], C[b], -1);
	
	swap(R[a], R[b]);
	swap(C[a], C[b]);
	A[R[a]][C[a]] = a;
	A[R[b]][C[b]] = b;
	
	AddCell(R[a], C[a], +1);
	AddCell(R[b], C[b], +1);
	return Get0();
}

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