Submission #274899

#	Time	Username	Problem	Language	Result	Execution time	Memory
274899		Haunted_Cpp	Seats (IOI18_seats)	C++17	5 / 100	4056 ms	90360 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 1e6 + 5;
 
class SegmentTree {
private:
  struct Node {
    int mn, mx;
    Node () {
      mx = -1e9;
      mn = 1e9;
    }
    void merge(Node esq, Node dir) {
      mn = min(esq.mn, dir.mn);
      mx = max(esq.mx, dir.mx);
    }
  };
  int LO, HI;
  vector<Node> seg;
  void build(int l, int r, int node, const vector<int> &arr) {
    if (l == r) {
      seg[node].mn = seg[node].mx = arr[l];
      return;
    }
    const int mid = l + (r - l) / 2;
    build(l, mid, 2 * node + 1, arr);
    build(mid + 1, r, 2 * node + 2, arr);
    seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
  }
  void modify(int l, int r, int where, int delta, int node) {
    if (l > where || r < where) return;
    if (l >= where && r <= where) {
      seg[node].mn = seg[node].mx = delta;
      return;
    }
    const int mid = l + (r - l) / 2; 
    modify(l, mid, where, delta, 2 * node + 1);
    modify(mid + 1, r, where, delta, 2 * node + 2);
    seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
  }
  Node query(int ql, int qr, int l, int r, int node) {
    if (l > qr || r < ql) return Node();
    if (l >= ql && r <= qr) return seg[node];
    const int mid = l + (r - l) / 2;
    Node esq = query(ql, qr, l, mid, 2 * node + 1);
    Node dir = query(ql, qr, mid + 1, r, 2 * node + 2);
    Node ans;
    ans.merge(esq, dir);
    return ans;
  }
public:
  void build(const vector<int> &arr) {
    LO = 0;
    HI = (int) arr.size() - 1;
    seg.clear();
    seg.resize(4 * (int)arr.size());
    build(LO, HI, 0, arr);
  }
  void modify(int where, int delta) {
    modify(LO, HI, where, delta, 0);
  }
  pair<int, int> query(int ql, int qr) {
    Node ans = query(ql, qr, LO, HI, 0);
    return {ans.mn, ans.mx};
  }
};
 
SegmentTree linhas, colunas;
 
int r, c;
vector<pair<int, int>> where;
 
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  r = H;
  c = W;
  linhas.build(R);
  colunas.build(C);
  where.resize(r * c);
  for (int i = 0; i < r * c; i++) {
    where[i] = {R[i], C[i]};
  }
}
 
int solve() {
  int res = 0;
  int min_row = 1e9;
  int max_row = -1e9;
  int min_column = 1e9;
  int max_column = -1e9;
  for (int i = 0; i < r * c; ) {
    pair<int, int> line = linhas.query(0, i);
    min_row = min(min_row, line.first);
    max_row = max(max_row, line.second);
    pair<int, int> col = colunas.query(0, i);
    min_column = min(min_column, col.first);
    max_column = max(max_column, col.second);
    const int cur = ((max_row - min_row + 1) * (max_column - min_column + 1));
    if (cur == i + 1) {
      ++res;
      ++i;
    } else {
      i = cur - 1;
    }
  }
  return res;
}
 
int swap_seats(int a, int b) {
  const int a_linha = where[a].first;
  const int b_linha = where[b].first;
  linhas.modify(a, b_linha);
  linhas.modify(b, a_linha);
  const int a_coluna = where[a].second;
  const int b_coluna = where[b].second;
  colunas.modify(a, b_coluna);
  colunas.modify(b, a_coluna);
  swap(where[a], where[b]);
  return solve();
}

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