Submission #835111

#	Time	Username	Problem	Language	Result	Execution time	Memory
835111		Johann	Seats (IOI18_seats)	C++14	0 / 100	4074 ms	72596 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;
  vi mini, maxi;
  void init(vi &A)
  {
    size = 1;
    while (size < sz(A))
      size *= 2;
    mini.assign(2 * size, INT_MAX);
    maxi.assign(2 * size, INT_MIN);
    for (int i = 0; i < sz(A); ++i)
      mini[i + size] = maxi[i + size] = A[i];
    for (int i = sz(A) - 1; i > 0; --i)
      maxi[i] = max(maxi[2 * i], maxi[2 * i + 1]), mini[i] = min(mini[2 * i], mini[2 * i + 1]);
  }
  void set(int i, int v)
  {
    i += size;
    mini[i] = maxi[i] = v;
    while (i >>= 1 > 0)
      maxi[i] = max(maxi[2 * i], maxi[2 * i + 1]), mini[i] = min(mini[2 * i], mini[2 * i + 1]);
  }
  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 {mini[x], maxi[x]};
    if (r <= lx || rx <= l)
      return {INT_MAX, INT_MIN};
    int m = (lx + rx) / 2;
    int mini1, mini2, maxi1, maxi2;
    tie(mini1, maxi1) = query(l, r, 2 * x, lx, m);
    tie(mini2, maxi2) = query(l, r, 2 * x + 1, m, rx);
    return {min(mini1, mini2), max(maxi1, maxi2)};
  }
};
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
      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