Submission #102847

#	Time	Username	Problem	Language	Result	Execution time	Memory
102847		wxh010910	Seats (IOI18_seats)	C++17	100 / 100	1880 ms	126008 KiB

seats

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

using namespace std;

class segtree_t {
 private:

  struct node_t {
    int tag, value, answer;
  };

  vector<node_t> tree;
  int n;

  void apply(int x, int value) {
    tree[x].tag += value;
    tree[x].value += value;
  }

  void push_up(int x, int z) {
    tree[x].value = min(tree[x + 1].value, tree[z].value);
    tree[x].answer = 0;
    if (tree[x].value == tree[x + 1].value) {
      tree[x].answer += tree[x + 1].answer;
    }
    if (tree[x].value == tree[z].value) {
      tree[x].answer += tree[z].answer;
    }
  }

  void push_down(int x, int z) {
    if (tree[x].tag) {
      apply(x + 1, tree[x].tag);
      apply(z, tree[x].tag);
      tree[x].tag = 0;
    }
  }

  void build(int x, int l, int r, vector<int> &a) {
    if (l == r) {
      tree[x].value = a[l];
      tree[x].answer = 1;
    } else {
      int y = l + r >> 1, z = x + (y - l + 1 << 1);
      build(x + 1, l, y, a);
      build(z, y + 1, r, a);
      push_up(x, z);
    }
  }

  void modify(int x, int l, int r, int ql, int qr, int value) {
    if (l == ql && r == qr) {
      apply(x, value);
    } else {
      int y = l + r >> 1, z = x + (y - l + 1 << 1);
      push_down(x, z);
      if (qr <= y) {
        modify(x + 1, l, y, ql, qr, value);
      } else if (ql > y) {
        modify(z, y + 1, r, ql, qr, value);
      } else {
        modify(x + 1, l, y, ql, y, value);
        modify(z, y + 1, r, y + 1, qr, value);
      }
      push_up(x, z);
    }
  }

 public:
  void init(vector<int> a) {
    n = a.size();
    tree.resize((n << 1) - 1);
    build(0, 0, n - 1, a);
  }

  void modify(int l, int r, int value) {
    if (l <= r) {
      modify(0, 0, n - 1, l, r, value);
    }
  }

  int query() {
    return tree[0].answer;
  }
};

const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};

vector<vector<int>> board;
segtree_t segtree;
vector<int> r, c;
int n, m;

bool in(int x, int y) {
  return x >= 0 && x < n && y >= 0 && y < m;
}

void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
  n = _n;
  m = _m;
  r = _r;
  c = _c;
  board = vector<vector<int>> (n, vector<int> (m));
  for (int i = 0; i < n * m; ++i) {
    board[r[i]][c[i]] = i;
  }
  vector<int> answer(n * m);
  int current = 0;
  for (int i = 0; i < n * m; ++i) {
    int x = r[i], y = c[i], degree = 0;
    for (int j = 0; j < 4; ++j) {
      int nx = x + dx[j], ny = y + dy[j];
      if (in(nx, ny)) {
        if (board[nx][ny] > i) {
          int degree = 0;
          for (int k = 0; k < 4; ++k) {
            int tx = nx + dx[k], ty = ny + dy[k];
            if (in(tx, ty) && board[tx][ty] <= i) {
              ++degree;
            }
          }
          if (degree == 2) {
            ++current;
          }
        } else {
          ++degree;
        }
      }
    }
    if (degree >= 2) {
      --current;
    }
    if (in(x, y + 1) && board[x][y + 1] <= i && (!in(x - 1, y + 1) || board[x - 1][y + 1] > i)) {
      --current;
    }
    if (in(x + 1, y) && board[x + 1][y] <= i && (!in(x + 1, y - 1) || board[x + 1][y - 1] > i)) {
      --current;
    }
    if ((!in(x - 1, y) || board[x - 1][y] > i) && (!in(x, y - 1) || board[x][y - 1] > i)) {
      ++current;
    }
    answer[i] = current;
  }
  segtree.init(answer);
}

void modify(int x, int y, int value) {
  vector<int> neighbor;
  {
    neighbor.clear();
    for (int i = 0; i < 4; ++i) {
      int nx = x + dx[i], ny = y + dy[i];
      if (in(nx, ny)) {
        neighbor.push_back(board[nx][ny]);
      }
    }
    sort(neighbor.begin(), neighbor.end());
    if (neighbor.size() >= 2) {
      segtree.modify(neighbor[1], board[x][y] - 1, -1);
      segtree.modify(neighbor[1], value - 1, 1);
    }
  }
  for (int i = 0; i < 4; ++i) {
    int nx = x + dx[i], ny = y + dy[i];
    if (in(nx, ny)) {
      neighbor.clear();
      for (int j = 0; j < 4; ++j) {
        int tx = nx + dx[j], ty = ny + dy[j];
        if (in(tx, ty)) {
          neighbor.push_back(board[tx][ty]);
        }
      }
      sort(neighbor.begin(), neighbor.end());
      if (neighbor.size() >= 2) {
        segtree.modify(neighbor[1], board[nx][ny] - 1, -1);
      }
      for (int j = 0; j < neighbor.size(); ++j) {
        if (neighbor[j] == board[x][y]) {
          neighbor[j] = value;
          break;
        }
      }
      sort(neighbor.begin(), neighbor.end());
      if (neighbor.size() >= 2) {
        segtree.modify(neighbor[1], board[nx][ny] - 1, 1);
      }
    }
  }
  {
    int bound = n * m;
    if (in(x - 1, y)) {
      bound = min(bound, board[x - 1][y]);
    }
    if (in(x, y - 1)) {
      bound = min(bound, board[x][y - 1]);
    }
    segtree.modify(board[x][y], bound - 1, -1);
    segtree.modify(value, bound - 1, 1);
  }
  if (in(x + 1, y)) {
    int bound = n * m;
    if (in(x + 1, y - 1)) {
      bound = min(bound, board[x + 1][y - 1]);
    }
    segtree.modify(board[x + 1][y], min(bound, board[x][y]) - 1, -1);
    segtree.modify(board[x + 1][y], min(bound, value) - 1, 1);
  }
  if (in(x, y + 1)) {
    int bound = n * m;
    if (in(x - 1, y + 1)) {
      bound = min(bound, board[x - 1][y + 1]);
    }
    segtree.modify(board[x][y + 1], min(bound, board[x][y]) - 1, -1);
    segtree.modify(board[x][y + 1], min(bound, value) - 1, 1);
  }
  board[x][y] = value;
}

int swap_seats(int a, int b) {
  modify(r[a], c[a], b);
  modify(r[b], c[b], a);
  swap(r[a], r[b]);
  swap(c[a], c[b]);
  return segtree.query();
}

Compilation message (stderr)

seats.cpp: In member function 'void segtree_t::build(int, int, int, std::vector<int>&)':
seats.cpp:45:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       int y = l + r >> 1, z = x + (y - l + 1 << 1);
               ~~^~~
seats.cpp:45:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
       int y = l + r >> 1, z = x + (y - l + 1 << 1);
                                    ~~~~~~^~~
seats.cpp: In member function 'void segtree_t::modify(int, int, int, int, int, int)':
seats.cpp:56:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       int y = l + r >> 1, z = x + (y - l + 1 << 1);
               ~~^~~
seats.cpp:56:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
       int y = l + r >> 1, z = x + (y - l + 1 << 1);
                                    ~~~~~~^~~
seats.cpp: In function 'void modify(int, int, int)':
seats.cpp:179:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < neighbor.size(); ++j) {
                       ~~^~~~~~~~~~~~~~~~~

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