Submission #777404

#	Time	Username	Problem	Language	Result	Execution time	Memory
777404		NeroZein	Seats (IOI18_seats)	C++17	25 / 100	2133 ms	65724 KiB

seats

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

const int N = 1003;

int n, m;
vector<vector<int>> a;

int seg[N + N][N << 1]; 

void upd (int nd, int l, int r, int p, int v, int ver) {
  if (l == r) {
    seg[ver][nd] = v;
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    upd(nd + 1, l, mid, p, v, ver); 
  } else {
    upd(rs, mid + 1, r, p, v, ver); 
  }
  seg[ver][nd] = max(seg[ver][nd + 1], seg[ver][rs]);
}

int qry (int nd, int l, int r, int s, int e, int ver) {
  if (l >= s && r <= e) {
    return seg[ver][nd];
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    return qry(nd + 1, l, mid, s, e, ver); 
  } else {
    if (mid < s) {
      return qry(rs, mid + 1, r, s, e, ver); 
    } else {
      return max(qry(nd + 1, l, mid, s, e, ver), qry(rs, mid + 1, r, s, e, ver));
    }
  }
}

int getver (int x, bool col) {
  return x + n * col; 
}

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int Dfs (int mx, int mxr, int mnr, int mxc, int mnc) {
  //cout << mx << ' ' << mxr << ' ' << mnr << ' ' << mxc << ' ' << mnc << '\n';
  int ret = 0; 
  if ((mxr - mnr + 1) * (mxc - mnc + 1) == mx + 1) {
    ret++; 
  }
  vector<int> nmxx(4, 1e9); 
  if (mxr + 1 < n) {
    int nmx = max(mx, qry(0, 0, m - 1, mnc, mxc, getver(mxr + 1, false))); 
    nmxx[0] = nmx; 
  }
  if (mnr - 1 >= 0) {
    int nmx = max(mx, qry(0, 0, m - 1, mnc, mxc, getver(mnr - 1, false)));
    nmxx[1] = nmx; 
  }
  if (mxc + 1 < m) {
    int nmx = max(mx, qry(0, 0, n - 1, mnr, mxr, getver(mxc + 1, true)));
    nmxx[2] = nmx; 
  }
  if (mnc - 1 >= 0) {
    int nmx = max(mx, qry(0, 0, n - 1, mnr, mxr, getver(mnc - 1, true))); 
    nmxx[3] = nmx; 
  }
  int mn = *min_element(nmxx.begin(), nmxx.end()); 
  if (nmxx[0] == mn && mn < 1e9) {
    ret += Dfs(mn, mxr + 1, mnr, mxc, mnc); 
  } else if (nmxx[1] == mn && mn < 1e9) {
    ret += Dfs(mn, mxr, mnr - 1, mxc, mnc); 
  } else if (nmxx[2] == mn && mn < 1e9) {
    ret += Dfs(mn, mxr, mnr, mxc + 1, mnc);     
  } else if (nmxx[3] == mn && mn < 1e9) {
    ret += Dfs(mn, mxr, mnr, mxc, mnc - 1); 
  }
  return ret; 
}

vector<int> r, c;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  n = H, m = W;
  r = R; c = C; 
  a.resize(n);
  for (int i = 0; i < n; ++i) {
    a[i].resize(m); 
  }
  for (int i = 0; i < n * m; ++i) {
    a[r[i]][c[i]] = i;
    upd(0, 0, m - 1, c[i], i, getver(r[i], false));
    upd(0, 0, n - 1, r[i], i, getver(c[i], true));
  }
}

int swap_seats(int x, int y) {
  upd(0, 0, m - 1, c[y], x, getver(r[y], false));
  upd(0, 0, n - 1, r[y], x, getver(c[y], true));
  upd(0, 0, m - 1, c[x], y, getver(r[x], false)); 
  upd(0, 0, n - 1, r[x], y, getver(c[x], true)); 
  swap(c[x], c[y]);
  swap(r[x], r[y]);
  return Dfs(0, r[0], r[0], c[0], c[0]); 
}

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