Submission #507645

#	Time	Username	Problem	Language	Result	Execution time	Memory
507645		jesus_coconut	Seats (IOI18_seats)	C++17	100 / 100	2123 ms	115176 KiB

seats

#include "seats.h"
#include <algorithm>
#include <numeric>
using namespace std;

struct LazySegTree {
  struct Item {
	int mn = 4, cnt_min = 0;

	Item friend operator+(Item const &lhs, Item const &rhs) {
	  if (lhs.mn == rhs.mn)
		return {lhs.mn, lhs.cnt_min + rhs.cnt_min};
	  if (lhs.mn < rhs.mn) return lhs;
	  return rhs;
	}

	Item friend operator*(Item const &lhs, int r) {
	  return {lhs.mn + r, lhs.cnt_min};
	}
  };

  int sz;
  Item const NE{1 << 28, 0};
  vector<Item> seg;
  vector<int> lazy;

  void upd(int l, int r, int val, int ver, int lx, int rx) {
	propagate(ver, lx, rx);
	if (r <= lx || rx <= l) return;
	if (l <= lx && rx <= r) {
	  seg[ver] = seg[ver] * val;
	  lazy[ver] += val;
	  return;
	}
	int mx = (lx + rx) / 2;
	upd(l, r, val, ver * 2 + 1, lx, mx);
	upd(l, r, val, ver * 2 + 2, mx, rx);
	seg[ver] = (seg[ver * 2 + 1] + seg[ver * 2 + 2]) * lazy[ver];
  }

  void build(vector<int> const &v, int ver, int lx, int rx) {
	if (rx - lx == 1) {
	  if (lx < size(v)) {
		seg[ver].mn = v[lx];
		seg[ver].cnt_min = 1;
	  }
	  return;
	}
	int mx = (lx + rx) / 2;
	build(v, ver * 2 + 1, lx, mx);
	build(v, ver * 2 + 2, mx, rx);
	seg[ver] = seg[ver * 2 + 1] + seg[ver * 2 + 2];
  }

  Item query(int l, int r, int ver, int lx, int rx) {
	propagate(ver, lx, rx);
	if (r <= lx || rx <= l) return NE;
	if (l <= lx && rx <= r) return seg[ver];
	int mx = (lx + rx) / 2;
	Item const &L = query(l, r, ver * 2 + 1, lx, mx);
	Item const &R = query(l, r, ver * 2 + 2, mx, rx);
	return (L + R) * lazy[ver];
  }

  void propagate(int ver, int lx, int rx) {
	if (rx - lx == 1) return;
	for (int i : {1, 2}) {
	  lazy[ver * 2 + i] += lazy[ver];
	  seg[ver * 2 + i] = seg[ver * 2 + i] * lazy[ver];
	}
	lazy[ver] = 0;
  }

  void resize(int _n) {
	sz = 1 << (32 - __builtin_clz(_n));
	seg.resize(sz * 2);
	lazy.resize(sz * 2);
  }

  int query() {
	return query(0, sz, 0, 0, sz).cnt_min;
  }

  void upd(int l, int r, int val) {
	if (r <= l) return;
	upd(l, r, val, 0, 0, sz);
  }

  void build(vector<int> const &v) {
	build(v, 0, 0, sz);
  }
};

vector<vector<int>> mat;
vector<int> r, c;
LazySegTree st;

array<int, 4> getArr(int x, int y) {
  array<int, 4> arr;
  for (int i = 0; i < 4; ++i) {
	arr[i] = mat[x - (i & 1)][y - ((i & 2) != 0)];
  }
  sort(begin(arr), end(arr));
  return arr;
}

void add(int x, int y, int val) {
  array<int, 4> const &arr = getArr(x, y);
  st.upd(arr[0], arr[1], val);
  st.upd(arr[2], arr[3], val);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  r = move(R);
  c = move(C);
  transform(begin(r), end(r), begin(r), [](int x) { return x + 1; });
  transform(begin(c), end(c), begin(c), [](int x) { return x + 1; });
  int mx = H * W;
  st.resize(mx);
  mat = vector(H + 2, vector(W + 2, mx));
  for (int i = 0; i < size(r); ++i) {
	mat[r[i]][c[i]] = i;
  }
  vector<int> dif(mx + 1);
  for (int i = 1; i <= H + 1; ++i) {
	for (int j = 1; j <= W + 1; ++j) {
	  array<int, 4> const &arr = getArr(i, j);
	  for (int k = 0; k < 4; ++k) {
		dif[arr[k]] += k % 2 ? -1 : 1;
	  }
	}
  }
  dif.pop_back();
  partial_sum(begin(dif), end(dif), begin(dif));
  st.build(dif);
}

int swap_seats(int a, int b) {
  for (int i = 0; i < 4; ++i) {
	add(r[a] + (i & 1), c[a] + ((i & 2) != 0), -1);
	add(r[b] + (i & 1), c[b] + ((i & 2) != 0), -1);
  }
  swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);
  swap(r[a], r[b]);
  swap(c[a], c[b]);
  for (int i = 0; i < 4; ++i) {
	add(r[a] + (i & 1), c[a] + ((i & 2) != 0), 1);
	add(r[b] + (i & 1), c[b] + ((i & 2) != 0), 1);
  }
  return st.query();
}

Compilation message (stderr)

seats.cpp: In member function 'void LazySegTree::build(const std::vector<int>&, int, int, int)':
seats.cpp:43:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if (lx < size(v)) {
      |        ~~~^~~~~~~~~
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:121:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   for (int i = 0; i < size(r); ++i) {
      |                   ~~^~~~~~~~~

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