제출 #802844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802844		IvanJ	자리 배치 (IOI18_seats)	C++17	100 / 100	3155 ms	127032 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e6 + 5;

int n, m, pot = 1;
ii pos[maxn];
vector<vector<int>> mat;
int L[maxn * 4];
ii T[maxn * 4];

ii merge(ii A, ii B) {
	if(A.x < B.x) return A;
	if(A.x > B.x) return B;
	return {A.x, A.y + B.y};
}

void prop(int x) {
	if(L[x] == 0) return;
	T[x].x += L[x];
	if(x < pot) 
		L[x * 2] += L[x], L[x * 2 + 1] += L[x];
	L[x] = 0;
}

void add_range(int x, int lo, int hi, int a, int b, int v) {
	prop(x);
	if(hi < a || b < lo) return;
	if(a <= lo && hi <= b) {
		L[x] += v;
		prop(x);
		return;
	}
	int mid = (lo + hi) / 2;
	add_range(x * 2, lo, mid, a, b, v);
	add_range(x * 2 + 1, mid + 1, hi, a, b, v);
	T[x] = merge(T[x * 2], T[x * 2 + 1]);
}

int answer() {
	if(T[1].x > 4) exit(1);
	return T[1].y;
}

int check(int x, int y) {return (x >= 0) & (x < n) & (y >= 0) & (y < m);}

void update(int x, int y, int val) {
	vector<int> v;
	if(check(x, y)) v.pb(mat[x][y]);
	if(check(x, y + 1)) v.pb(mat[x][y + 1]);
	if(check(x + 1, y)) v.pb(mat[x + 1][y]);
	if(check(x + 1, y + 1)) v.pb(mat[x + 1][y + 1]);
	v.pb(n * m);
	sort(all(v));
	add_range(1, 0, pot - 1, v[0], v[1] - 1, 1 * val);
	if(v.size() >= 4) 
		add_range(1, 0, pot - 1, v[2], v[3] - 1, 3 * val);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	n = H, m = W;
	while(pot < (n * m)) pot <<= 1;
	for(int i = 0;i < n * m;i++) T[i + pot].y = 1;
	for(int i = n * m;i < (pot << 1);i++) T[i + pot].x = 1e9;
	for(int i = pot - 1;i > 0;i--) T[i] = merge(T[i * 2], T[i * 2 + 1]);
	for(int i = 0;i < n;i++) 
		mat.pb(vector<int>(m, 0));
		
	for(int i = 0;i < n * m;i++) 
		mat[R[i]][C[i]] = i, pos[i] = {R[i], C[i]};
	
	for(int i = -1;i < n;i++) 
		for(int j = -1;j < m;j++) 
			update(i, j, 1);
}

int swap_seats(int a, int b) {
	set<ii> s;
	for(int i = 0;i < 2;i++)
		for(int j = 0;j < 2;j++) {
			s.insert({pos[a].x - i, pos[a].y - j});
			s.insert({pos[b].x - i, pos[b].y - j});
		}
	
	for(ii p : s) update(p.x, p.y, -1);
	swap(mat[pos[a].x][pos[a].y], mat[pos[b].x][pos[b].y]);
	swap(pos[a], pos[b]);
	for(ii p : s) update(p.x, p.y, +1);
	return answer();
}

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