Submission #835150

#	Time	Username	Problem	Language	Result	Execution time	Memory
835150		Johann	Seats (IOI18_seats)	C++14	0 / 100	238 ms	98852 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 = sz(A) - 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;

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);
}

int swap_seats(int a, int 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 rmax = R[0], rmin = R[0];
  int cmax = C[0], cmin = C[0];
  int ans = 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)
      ++ans, ++k;
    else
    {
      assert(area - 1 > k);
      k = area - 1;
    }
  }

  return ans;
}

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