Submission #103047

#	Time	Username	Problem	Language	Result	Execution time	Memory
103047		KCSC	Seats (IOI18_seats)	C++14	100 / 100	2439 ms	129688 KiB

seats

#ifndef HOME
	#include "seats.h"
#endif

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

#ifdef HOME
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace
#endif

const int DIM = 1000005;

struct Node {
	int mnm, cnt, lzy;

	Node(int _mnm = 0, int _cnt = 0, int _lzy = 0) :
		mnm(_mnm), cnt(_cnt), lzy(_lzy) {}
} sgt[DIM << 2];

vector<vector<int>> mat; 
pair<int, int> pos[DIM];

int n, m, psm[DIM];

void build(int nd, int le, int ri) {
	if (le == ri) {
		sgt[nd] = Node(psm[le], 1); }
	else {
		int md = (le + ri) >> 1;
		build(nd << 1, le, md);
		build(nd << 1 | 1, md + 1, ri);
		sgt[nd].mnm = min(sgt[nd << 1].mnm, sgt[nd << 1 | 1].mnm);
		if (sgt[nd].mnm == sgt[nd << 1].mnm) {
			sgt[nd].cnt += sgt[nd << 1].cnt; }
		if (sgt[nd].mnm == sgt[nd << 1 | 1].mnm) {
			sgt[nd].cnt += sgt[nd << 1 | 1].cnt; } } }

int _st, _en, _vl;
void update(int nd, int le, int ri) {
	if (sgt[nd].lzy) {
		sgt[nd].mnm += sgt[nd].lzy;
		if (le != ri) {
			sgt[nd << 1].lzy += sgt[nd].lzy;
			sgt[nd << 1 | 1].lzy += sgt[nd].lzy; }
		sgt[nd].lzy = 0; } 
	if (ri < _st or _en < le or _st > _en) {
		return; }
	if (_st <= le and ri <= _en) {
		sgt[nd].mnm += _vl;
		if (le != ri) {
			sgt[nd << 1].lzy += _vl;
			sgt[nd << 1 | 1].lzy += _vl; } } 
	else {
		int md = (le + ri) >> 1;
		update(nd << 1, le, md);
		update(nd << 1 | 1, md + 1, ri);
		sgt[nd].mnm = min(sgt[nd << 1].mnm, sgt[nd << 1 | 1].mnm);
		sgt[nd].cnt = 0;
		if (sgt[nd].mnm == sgt[nd << 1].mnm) {
			sgt[nd].cnt += sgt[nd << 1].cnt; }
		if (sgt[nd].mnm == sgt[nd << 1 | 1].mnm) {
			sgt[nd].cnt += sgt[nd << 1 | 1].cnt; } } }

void updateSquare(int x, int y, int vl = 1, bool ok = true) {
	vector<int> arr;
	arr.push_back(mat[x][y]); arr.push_back(mat[x + 1][y + 1]);
	arr.push_back(mat[x][y + 1]); arr.push_back(mat[x + 1][y]);
	sort(arr.begin(), arr.end());
	if (ok) {
		_st = arr[0]; _en = arr[1] - 1; _vl = vl * 1;
		update(1, 0, n * m - 1);
		_st = arr[2]; _en = arr[3] - 1; _vl = vl * 5;
		update(1, 0, n * m - 1); }
	else {
		psm[arr[0]] += vl * 1; psm[arr[1]] -= vl * 1;
		psm[arr[2]] += vl * 5; psm[arr[3]] -= vl * 5; } }

void give_initial_chart(int h, int w, vector<int> R, vector<int> C) {
	n = h; m = w;
	mat.resize(n + 2, vector<int>(m + 2, n * m));
	for (int i = 0; i < n * m; ++i) {
		++R[i]; ++C[i]; mat[R[i]][C[i]] = i; 
		pos[i] = make_pair(R[i], C[i]); }
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= m; ++j) {
			updateSquare(i, j, 1, false); } } 
	for (int i = 1; i < n * m; ++i) {
		psm[i] += psm[i - 1]; }
	build(1, 0, n * m - 1); }

int swap_seats(int a, int b) {
	set<pair<int, int>> sqr;
	for (int i = -1; i <= 0; ++i) {
		for (int j = -1; j <= 0; ++j) {
			sqr.insert(make_pair(pos[a].first + i, pos[a].second + j));
			sqr.insert(make_pair(pos[b].first + i, pos[b].second + j)); } }
	for (auto sq : sqr) {
		updateSquare(sq.first, sq.second, -1); }
	swap(mat[pos[a].first][pos[a].second], mat[pos[b].first][pos[b].second]);
	swap(pos[a], pos[b]);
	for (auto sq : sqr) {
		updateSquare(sq.first, sq.second, 1); }
	return sgt[1].mnm == 4 ? sgt[1].cnt : 0; }

#ifdef HOME
int main() {
	freopen("seats.in", "r", stdin);
	freopen("seats.out", "w", stdout);
  int H = read_int();
  int W = read_int();
  int Q = read_int();
  std::vector<int> R(H * W), C(H * W);
  for (int i = 0; i < H * W; ++i) {
    R[i] = read_int();
    C[i] = read_int();
  }
  std::vector<int> A(Q), B(Q);
  for (int j = 0; j < Q; ++j) {
    A[j] = read_int();
    B[j] = read_int();
  }

  give_initial_chart(H, W, R, C);
  for (int j = 0; j < Q; ++j) {
    int answer = swap_seats(A[j], B[j]);
    printf("%d\n", answer);
  }
  return 0;
}
#endif

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