Submission #794298

#	Time	Username	Problem	Language	Result	Execution time	Memory
794298		ymm	Seats (IOI18_seats)	C++17	100 / 100	2614 ms	119120 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 1<<20;
namespace seg {
	struct {
		int mn, cnt, val;
	} t[N*4];
	int sz;

	void merge(int i) {
		t[i].mn = min(t[2*i+1].mn, t[2*i+2].mn);
		t[i].cnt =   (t[2*i+1].mn == t[i].mn? t[2*i+1].cnt: 0)
		           + (t[2*i+2].mn == t[i].mn? t[2*i+2].cnt: 0);
		t[i].mn += t[i].val;
	}
	void add(int l, int r, int x, int i, int b, int e) {
		if (l <= b && e <= r) {
			t[i].mn += x;
			t[i].val += x;
			return;
		}
		if (r <= b || e <= l)
			return;
		add(l, r, x, 2*i+1, b, (b+e)/2);
		add(l, r, x, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void add(int l, int r, int x) { if (l < r) add(l, r, x, 0, 0, sz); }
	void init(int i, int b, int e) {
		t[i].mn = t[i].val = 0;
		t[i].cnt = e-b;
		if (e-b > 1) {
			init(2*i+1, b, (b+e)/2);
			init(2*i+2, (b+e)/2, e);
		}
	}
	void init(int n) { sz = n; init(0, 0, sz); }
}

vector<vector<int>> a;
pii pos[N];
int n, m;

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

void add_sq(int i, int j, int mul)
{
	vector<int> vec;
	Loop (x,i,i+2) Loop (y,j,j+2)
		vec.push_back(in(x, y)? a[x][y]: n*m);
	sort(vec.begin(), vec.end());
	seg::add(vec[0], vec[1], mul);
	seg::add(vec[2], vec[3], mul);
}

void add_adj(int i, int j, int mul)
{
	Loop (x,i-1,i+1) Loop (y,j-1,j+1)
		add_sq(x, y, mul);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	n = H;
	m = W;
	a.assign(n, vector<int>(m));
	Loop (i,0,n*m) {
		pos[i] = {R[i], C[i]};
		a[R[i]][C[i]] = i;
	}
	seg::init(n*m);
	Loop (i,-1,n+1) Loop (j,-1,m+1)
		add_sq(i, j, 1);
}

int swap_seats(int a, int b) {
	auto [x1, y1] = pos[a];
	auto [x2, y2] = pos[b];
	add_adj(x1, y1, -1);
	::a[x1][y1] = b;
	add_adj(x1, y1, 1);
	add_adj(x2, y2, -1);
	::a[x2][y2] = a;
	add_adj(x2, y2, 1);
	swap(pos[a], pos[b]);
	return seg::t[0].cnt;
}

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