Submission #422199

#	Time	Username	Problem	Language	Result	Execution time	Memory
422199		Tangent	Seats (IOI18_seats)	C++17	0 / 100	4073 ms	70996 KiB

seats

#include "seats.h"
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;

#define ffor(i, a, b) for (ll i = a; i < b; i++)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()

int n, h, w, r[1000000], c[1000000], rmin[2000000], rmax[2000000], cmin[2000000], cmax[2000000];

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  h = H;
  w = W;
  n = R.size();
  rep(i, n) {
    r[i] = rmin[n + i] = rmax[n + i] = R[i];
    c[i] = cmin[n + i] = cmax[n + i] = C[i];
  }

  for (int i = n - 1; i > 0; i--) {
    rmin[i] = min(rmin[i * 2], rmin[i * 2 + 1]);
    rmax[i] = max(rmax[i * 2], rmax[i * 2 + 1]);
    cmin[i] = min(cmin[i * 2], cmin[i * 2 + 1]);
    cmax[i] = max(cmax[i * 2], cmax[i * 2 + 1]);
  }
}

int swap_seats(int a, int b) {
  rmin[n + a] = rmax[n + a] = r[b];
  cmin[n + a] = cmax[n + a] = c[b];
  rmin[n + b] = rmax[n + b] = r[a];
  cmin[n + b] = cmax[n + b] = c[a];
  swap(r[a], r[b]);
  swap(c[a], c[b]);

  int i = n + a;
  while (i > 1) {
    i /= 2;
    rmin[i] = min(rmin[i * 2], rmin[i * 2 + 1]);
    rmax[i] = max(rmax[i * 2], rmax[i * 2 + 1]);
    cmin[i] = min(cmin[i * 2], cmin[i * 2 + 1]);
    cmax[i] = max(cmax[i * 2], cmax[i * 2 + 1]);
  }

  int res = 2;
  i = 2;
  while(i < n) {
    int ra = n, rb = -1, ca = n, cb = -1, lo = n, hi = n + i;
    while (lo < hi) {
      if (lo % 2) {
        ra = min(ra, rmin[lo]);
        rb = max(rb, rmax[lo]);
        ca = min(ca, cmin[lo]);
        cb = max(cb, cmax[lo++]);
      }
      if (hi % 2) {
        ra = min(ra, rmin[--hi]);
        rb = max(rb, rmax[hi]);
        ca = min(ca, cmin[hi]);
        cb = max(cb, cmax[hi]);
      }
      lo /= 2;
      hi /= 2;
    }
    if ((rb - ra + 1) * (cb - ca + 1) == i) {
      res++;
      i++;
    } else {
      i = (rb - ra + 1) * (cb - ca + 1);
    }
  }
  return res;
}

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