Submission #103040

#	Time	Username	Problem	Language	Result	Execution time	Memory
103040		KCSC	Seats (IOI18_seats)	C++14	37 / 100	4098 ms	184968 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;
const int INF = 1000000005;

struct Node {
	long long mnm, cnt, lzy;

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

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

int n, m;

void updateLazy(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; } }

Node updateNode(Node lson, Node rson) {
	Node ans; ans.mnm = min(lson.mnm, rson.mnm);
	if (ans.mnm == lson.mnm) {
		ans.cnt += lson.cnt; }
	if (ans.mnm == rson.mnm) {
		ans.cnt += rson.cnt; }
	return ans; }

void build(int nd, int le, int ri) {
	sgt[nd].cnt = ri - le + 1;
	if (le != ri) {
		int md = (le + ri) >> 1;
		build(nd << 1, le, md);
		build(nd << 1 | 1, md + 1, ri); } }

void update(int nd, int le, int ri, int st, int en, int vl) {
	updateLazy(nd, le, ri);
	if (ri < st or en < le or st > en) {
		return; }
	if (st <= le and ri <= en) {
		sgt[nd].lzy += vl;
		updateLazy(nd, le, ri); }
	else {
		int md = (le + ri) >> 1;
		update(nd << 1, le, md, st, en, vl);
		update(nd << 1 | 1, md + 1, ri, st, en, vl);
		sgt[nd] = updateNode(sgt[nd << 1], sgt[nd << 1 | 1]); } }

void updateSquare(int x, int y, int vl = 1) {
	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());
	update(1, 0, n * m - 1, arr[0], arr[1] - 1, vl);
	update(1, 0, n * m - 1, arr[2], arr[3] - 1, INF * vl); }

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]); }
	build(1, 0, n * m - 1);
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= m; ++j) {
			updateSquare(i, j); } } }

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: 0 / 33
• Subtask 6: 0 / 30