Submission #1041154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041154		Soumya1	Seats (IOI18_seats)	C++17	100 / 100	3501 ms	119380 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e6 + 5;
int t[4 * mxN][2], lazy[4 * mxN];
void push(int x, int lx, int rx) {
  if (lx == rx) return;
  t[x << 1][0] += lazy[x];
  t[x << 1 | 1][0] += lazy[x];
  lazy[x << 1] += lazy[x];
  lazy[x << 1 | 1] += lazy[x];
  lazy[x] = 0;
}
void build(int x, int lx, int rx) {
  if (lx == rx) {
    t[x][1] = 1;
    return;
  }
  int mx = (lx + rx) >> 1;
  build(x << 1, lx, mx);
  build(x << 1 | 1, mx + 1, rx);
  t[x][1] = t[x << 1][1] + t[x << 1 | 1][1];
}
void update(int x, int lx, int rx, int l, int r, int del) {
  if (lazy[x]) push(x, lx, rx);
  if (l > rx || lx > r) return;
  if (l <= lx && r >= rx) {
    t[x][0] += del;
    lazy[x] += del;
    return;
  }
  int mx = (lx + rx) >> 1;
  update(x << 1, lx, mx, l, r, del);
  update(x << 1 | 1, mx + 1, rx, l, r, del);
  t[x][0] = min(t[x << 1][0], t[x << 1 | 1][0]);
  t[x][1] = 0;
  if (t[x][0] == t[x << 1][0]) t[x][1] += t[x << 1][1];
  if (t[x][0] == t[x << 1 | 1][0]) t[x][1] += t[x << 1 | 1][1];
}
vector<vector<int>> mat;
vector<int> r, c;
vector<vector<array<int, 2>>> all = {
  {{-1, 0}, {0, 1}}, 
  {{0, 1}, {1, 0}}, 
  {{1, 0}, {0, -1}},
  {{0, -1}, {-1, 0}}
};
int H, W;
void add(int x, int y, int del) {
  if (!x || !y || x == H + 1 || y == W + 1) return;
  for (int i = 0; i < 4; i++) {
    int mx = H * W + 1;
    int mn = 0;
    for (auto a : all[i]) {
      mx = min(mx, mat[x + a[0]][y + a[1]]);
      mn = max(mn, mat[x + a[0]][y + a[1]]);
    }
    if (mx > mat[x][y]) update(1, 1, H * W, mat[x][y] + 1, mx, del);
    if (mn < mat[x][y]) update(1, 1, H * W, mn + 1, mat[x][y], del);
  }
}
void give_initial_chart(int _H, int _W, std::vector<int> R, std::vector<int> C) {
  H = _H, W = _W;
  mat.assign(H + 2, vector<int> (W + 2, H * W));
  for (int i = 0; i < H * W; i++) {
    R[i]++, C[i]++;
    mat[R[i]][C[i]] = i;
  }
  build(1, 1, H * W);
  r = R, c = C;
  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      add(i, j, 1);
    }
  }
}
int swap_seats(int a, int b) {
  vector<pair<int, int>> cells = {{r[a], c[a]}, {r[b], c[b]}};
  for (int i = 0; i < 2; i++) {
    for (int dx = -1; dx <= 1; dx++) {
      for (int dy = -1; dy <= 1; dy++) {
        int x = cells[i].first + dx, y = cells[i].second + dy;
        cells.push_back({x, y});
      }
    }
  }
  sort(cells.begin(), cells.end());
  cells.erase(unique(cells.begin(), cells.end()), cells.end());
  for (auto [x, y] : cells) add(x, y, -1);
  swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);
  swap(r[a], r[b]);
  swap(c[a], c[b]);
  for (auto [x, y] : cells) add(x, y, 1);
  return t[1][1];
}

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