Submission #222611

#	Time	Username	Problem	Language	Result	Execution time	Memory
222611		rama_pang	Seats (IOI18_seats)	C++14	100 / 100	2488 ms	133880 KiB

seats

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

class SegmentTree {
 private:
  struct Data {
    pair<int, int> value;
    int cnt;

    Data() {}
    Data(pair<int, int> v, int c) : value(v), cnt(c) {}

    friend Data Merge(const Data &a, const Data &b) {
      if (a.value < b.value) {
        return a;
      } else if (a.value > b.value) {
        return b;
      } else {
        return Data(a.value, a.cnt + b.cnt);
      }
    }
  };

  int sz;
  vector<Data> tree;
  vector<pair<int, int>> lazy;

  void Apply(int n, int a, int b) {
    tree[n].value.first += a;
    tree[n].value.second += b;
    lazy[n].first += a;
    lazy[n].second += b;
  }

  void Push(int n, int lc, int rc) {
    Apply(lc, lazy[n].first, lazy[n].second);
    Apply(rc, lazy[n].first, lazy[n].second);
    lazy[n].first = lazy[n].second = 0;
  }

  void Pull(int n, int lc, int rc) {
    tree[n] = Merge(tree[lc], tree[rc]);
  }

  void Update(int n, int tl, int tr, int l, int r, int a, int b) {
    if (tr < l || r < tl || tl > tr || l > r) return;
    if (l <= tl && tr <= r) return Apply(n, a, b);
    int mid = (tl + tr) / 2;
    int lc = n + 1;
    int rc = n + 2 * (mid - tl + 1);
    Push(n, lc, rc);
    Update(lc, tl, mid, l, r, a, b);
    Update(rc, mid + 1, tr, l, r, a, b);
    Pull(n, lc, rc);
  }

  void Build(int n, int tl, int tr) {
    if (tl == tr) return void(tree[n] = Data({0, 0}, 1));
    int mid = (tl + tr) / 2;
    int lc = n + 1;
    int rc = n + 2 * (mid - tl + 1);
    Build(lc, tl, mid);
    Build(rc, mid + 1, tr);
    Pull(n, lc, rc);
  }

 public:
  SegmentTree() {}
  SegmentTree(int n) : sz(n) {
    tree.resize(2 * sz);
    lazy.resize(2 * sz);
    Build(1, 0, sz - 1);
  }

  void Update(int l, int r, int a, int b) {
    return Update(1, 0, sz - 1, l, r, a, b);
  }

  int Query() {
    return tree[1].value == make_pair(4, 0) ? tree[1].cnt : 0; // 4 squares with 1 black cell, 0 squares with 3 black cells
  }
};

int H, W;
vector<int> R, C; // Rows and Columns of each student
vector<vector<int>> A; // The seating chart

SegmentTree SegTree;

int get_value(int i, int j) {
  if (!(0 <= i && i < H && 0 <= j && j < W)) return H * W;
  return A[i][j];
}

int square_count(int r, int c, int a) { // count black squares in 2-by-2 square, where the top left corner is (r, c)
  int res = 0; // values <= a is considered a black square
  if (get_value(r,     c    ) <= a) res++;
  if (get_value(r + 1, c    ) <= a) res++;
  if (get_value(r,     c + 1) <= a) res++;
  if (get_value(r + 1, c + 1) <= a) res++;
  return res;
}

void update(int r, int c, int sgn) {
  vector<int> cnt(5, 0);
  
  cnt[square_count(r - 1, c - 1, get_value(r, c) - 1)] -= sgn;
  cnt[square_count(r    , c - 1, get_value(r, c) - 1)] -= sgn;
  cnt[square_count(r - 1, c    , get_value(r, c) - 1)] -= sgn;
  cnt[square_count(r    , c    , get_value(r, c) - 1)] -= sgn;
  
  cnt[square_count(r - 1, c - 1, get_value(r, c))] += sgn;
  cnt[square_count(r    , c - 1, get_value(r, c))] += sgn;
  cnt[square_count(r - 1, c    , get_value(r, c))] += sgn;
  cnt[square_count(r    , c    , get_value(r, c))] += sgn;
  
  SegTree.Update(get_value(r, c), H * W - 1, cnt[1], cnt[3]);
}

void give_initial_chart(int H_, int W_, vector<int> R_, vector<int> C_) {
  H = H_, W = W_, R = R_, C = C_;
  SegTree = SegmentTree(H * W);
  A.assign(H, vector<int>(W, H * W));

  for (int i = 0; i < H * W; i++) {
    A[R[i]][C[i]] = i;
    update(R[i], C[i], +1);
  }
}

int swap_seats(int a, int b) {
  vector<pair<int, int>> ls; // list of affected cells
  for (int x = -1; x <= 1; x++) {
    for (int y = -1; y <= 1; y++) {
      ls.emplace_back(R[a] + x, C[a] + y);
      ls.emplace_back(R[b] + x, C[b] + y);
    }
  }
  sort(begin(ls), end(ls));
  ls.resize(unique(begin(ls), end(ls)) - begin(ls));

  for (auto i : ls) update(i.first, i.second, -1);
  swap(R[a], R[b]), swap(C[a], C[b]);
  swap(A[R[a]][C[a]], A[R[b]][C[b]]);
  for (auto i : ls) update(i.first, i.second, +1);
  
  return SegTree.Query();
}

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