Submission #888936

#	Time	Username	Problem	Language	Result	Execution time	Memory
888936		nguyentunglam	Seats (IOI18_seats)	C++17	100 / 100	2744 ms	131408 KiB

seats

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define all(v) v.begin(), v.end()

using namespace std;

const int N = 1e6 + 10, M = 1010;

int r[N], c[N], order[4];

vector<vector<int> > a;

int h, w;

int f[N << 2], g[N << 2], lazy[N << 2];

void push(int s, int l, int r) {
  if (!lazy[s]) return;
  f[s] += lazy[s];
  if (l != r) {
    lazy[s << 1] += lazy[s];
    lazy[s << 1 | 1] += lazy[s];
  }
  lazy[s] = 0;
}

void up(int s, int l, int r, int from, int to, int val) {
  push(s, l, r);
  if (l > to || r < from) return;
  if (from <= l && r <= to) {
    lazy[s] = val;
    push(s, l, r);
    return;
  }
  int mid = l + r >> 1;
  up(s << 1, l, mid, from, to, val);
  up(s << 1 | 1, mid + 1, r, from, to, val);
  f[s] = min(f[s << 1], f[s << 1 | 1]);
  g[s] = (f[s] == f[s << 1]) * g[s << 1] + (f[s] == f[s << 1 | 1]) * g[s << 1 | 1];
}

void update (int x, int y, int val) {
  order[0] = a[x][y];
  order[1] = a[x + 1][y];
  order[2] = a[x][y + 1];
  order[3] = a[x + 1][y + 1];
  order[4] = h * w + 1;
  sort(order, order + 4);
  int one = 0, three = 0, cnt = 0;
  for(int i = 0; i < 4; i++) {
    cnt += order[i] > 0;
    if (cnt == 1) up(1, 1, h * w, order[i], order[i + 1] - 1, val);
    if (cnt == 3) up(1, 1, h * w, order[i], order[i + 1] - 1, val * 5);
  }
}

void give_initial_chart(int _h, int _w, vector<int> _r, vector<int> _c) {
  h = _h; w = _w;
  a = vector<vector<int> > (h + 2, vector<int> (w + 2));
  for(int i = 1; i <= h * w; i++) {
    r[i] = _r[i - 1] + 1, c[i] = _c[i - 1] + 1;
    a[r[i]][c[i]] = i;
  }

  for(int i = 1; i <= 4 * h * w; i++) g[i] = 1;

  for(int i = 0; i <= h; i++) for(int j = 0; j <= w; j++) update(i, j, 1);

//   for(int i = 0; i < h * w; i++) cout << r[i] << " " << c[i] << endl;
}

void change (int x, int y, int val) {
  update(x - 1, y - 1, val);
  update(x, y - 1, val);
  update(x - 1, y, val);
  update(x, y, val);
}

int swap_seats(int x, int y) {
  ++x; ++y;

  change(r[x], c[x], -1);
  a[r[x]][c[x]] = y;
  change(r[x], c[x], 1);

  change(r[y], c[y], -1);
  a[r[y]][c[y]] = x;
  change(r[y], c[y], 1);

  swap(r[x], r[y]);
  swap(c[x], c[y]);

  return g[1];
}

#ifdef ngu
int main() {
   freopen ("task.inp", "r", stdin);
   freopen ("task.out", "w", stdout);

   int _h, _w; cin >> _h >> _w;
   vector<int> _r(_h * _w), _c(_h * _w);
   for(int i = 0; i < _h; i++) for(int j = 0; j < _w; j++) {
      int x; cin >> x;
      _r[x] = i;
      _c[x] = j;
   }

   give_initial_chart(_h, _w, _r, _c);

   int q; cin >> q;

   while (q--) {
      int a, b; cin >> a >> b;
      cout << swap_seats(a, b) << endl;
   }
}
#endif // ngu

Compilation message (stderr)

seats.cpp: In function 'void up(int, int, int, int, int, int)':
seats.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid = l + r >> 1;
      |             ~~^~~
seats.cpp: In function 'void update(int, int, int)':
seats.cpp:52:7: warning: unused variable 'one' [-Wunused-variable]
   52 |   int one = 0, three = 0, cnt = 0;
      |       ^~~
seats.cpp:52:16: warning: unused variable 'three' [-Wunused-variable]
   52 |   int one = 0, three = 0, cnt = 0;
      |                ^~~~~
seats.cpp:50:10: warning: array subscript 4 is above array bounds of 'int [4]' [-Warray-bounds]
   50 |   order[4] = h * w + 1;
      |   ~~~~~~~^
seats.cpp:12:17: note: while referencing 'order'
   12 | int r[N], c[N], order[4];
      |                 ^~~~~

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