제출 #835727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835727		Johann	자리 배치 (IOI18_seats)	C++14	17 / 100	4072 ms	76584 KiB

seats

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int H, W;
std::vector<int> R, C;
struct segtree
{
  int size;
  vpii arr;
  const pii NEUTRAL = {1 << 30, -(1 << 30)};
  void init(vi &A)
  {
    size = 1;
    while (size < sz(A))
      size *= 2;
    arr.assign(2 * size, NEUTRAL);
    for (int i = 0; i < sz(A); ++i)
      arr[i + size] = {A[i], A[i]};
    for (int i = size - 1; i > 0; --i)
      arr[i] = combine(arr[2 * i], arr[2 * i + 1]);
  }
  pii combine(const pii &a, const pii &b)
  {
    return {min(a.first, b.first), max(a.second, b.second)};
  }
  void set(int i, int v)
  {
    i += size;
    arr[i] = {v, v};
    i /= 2;
    while (i > 0)
    {
      arr[i] = combine(arr[2 * i], arr[2 * i + 1]);
      i /= 2;
    }
  }
  pii query(int l, int r) { return query(l, r, 1, 0, size); }
  pii query(int l, int r, int x, int lx, int rx)
  {
    if (l <= lx && rx <= r)
      return arr[x];
    if (r <= lx || rx <= l)
      return NEUTRAL;
    int m = (lx + rx) / 2;
    pii left = query(l, r, 2 * x, lx, m);
    pii right = query(l, r, 2 * x + 1, m, rx);
    return combine(left, right);
  }
};
segtree segR;
segtree segC;

struct fenwick
{
  vi arr;
  void init(int size)
  {
    arr.assign(size + 1, 0);
  }
  void add(int i, int v)
  {
    ++i;
    while (i < sz(arr))
      arr[i] += v, i += i & (~i + 1);
  }
  int query(int l, int r) { return query(r - 1) - ((l > 0) ? query(l - 1) : 0); }
  int query(int i)
  {
    ++i;
    int ans = 0;
    while (i > 0)
      ans += arr[i], i -= i & (~i + 1);
    return ans;
  }
};
fenwick fen;

void give_initial_chart(int _H, int _W, std::vector<int> _R, std::vector<int> _C)
{
  H = _H, W = _W;
  R = _R, C = _C;
  segR.init(R), segC.init(C);
  fen.init(H * W);

  int rmax = R[0], rmin = R[0];
  int cmax = C[0], cmin = C[0];
  int k = 0;
  while (k < H * W)
  {
    tie(rmin, rmax) = segR.query(0, k + 1);
    tie(cmin, cmax) = segC.query(0, k + 1);
    int area = (rmax - rmin + 1) * (cmax - cmin + 1);
    if (area == k + 1)
      fen.add(k, 1), ++k;
    else
    {
      assert(area - 1 > k);
      k = area - 1;
    }
  }
}

int swap_seats(int a, int b)
{
  if (a > b)
    swap(a, b);
  swap(R[a], R[b]), swap(C[a], C[b]);
  segR.set(a, R[a]);
  segC.set(a, C[a]);
  segR.set(b, R[b]);
  segC.set(b, C[b]);

  int rmin, rmax, cmin, cmax;
  tie(rmin, rmax) = segR.query(0, a + 1);
  tie(cmin, cmax) = segC.query(0, a + 1);
  for (int k = a; k < b + 1; ++k)
  {
    if (fen.query(k, k + 1))
      fen.add(k, -1);
    rmax = max(rmax, R[k]);
    rmin = min(rmin, R[k]);
    cmax = max(cmax, C[k]);
    cmin = min(cmin, C[k]);
    int area = (rmax - rmin + 1) * (cmax - cmin + 1);
    if (area == k + 1)
      fen.add(k, 1);
  }

  return fen.query(0, H * W);
}

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