Submission #1307729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307729		madamadam3	Seats (IOI18_seats)	C++20	31 / 100	4096 ms	94532 KiB

seats

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

using namespace std;

using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;

struct Node {
  int r1, r2, c1, c2;
  Node() : r1(INT_MAX), r2(INT_MIN), c1(INT_MAX), c2(INT_MIN) {}
  Node(int r, int c) {
    r1 = r2 = r; c1 = c2 = c;
  }

  Node(Node left, Node right) {
    r1 = min(left.r1, right.r1); r2 = max(left.r2, right.r2);
    c1 = min(left.c1, right.c1); c2 = max(left.c2, right.c2);
  }

  int area() {
    return (r2 - r1 + 1) * (c2 - c1 + 1);
  }
};

struct SegTree {
  int n; vi row, col; vector<Node> st;

  SegTree() {};
  SegTree(int N, vi &R, vi &C) {
    n = N; row = R; col = C; st.resize(4*n);
    build(0, 0, n);
  }

  Node build(int i, int l, int r) {
    if (l+1 == r) return st[i] = Node(row[l], col[l]);

    int m = l + (r - l) / 2;
    return st[i] = Node(build(2*i+1, l, m), build(2*i+2, m, r));
  }

  Node query(int i, int l, int r, int ql, int qr) {
    if (r <= ql || qr <= l) return Node();
    if (ql <= l && r <= qr) return st[i];

    int m = l + (r - l) / 2;
    return Node(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr));
  }

  Node update(int i, int l, int r, int k, int x, int y) {
    if (!(l <= k && k < r)) return st[i];
    if (l+1 == r) {
      row[k] = x; col[k] = y;
      return st[i] = Node(x, y);
    }

    int m = l + (r - l) / 2;
    return st[i] = Node(update(2*i+1, l, m, k, x, y), update(2*i+2, m, r, k, x, y));
  }
};

int n, h, w;
vi r, c;
SegTree st;

void give_initial_chart(int H, int W, vi R, vi C) {
  h = H, w = W, n = h*w;
  r = R, c = C;
  st = SegTree(n, r, c);
}

int swap_seats(int a, int b) {
  swap(r[a], r[b]); swap(c[a], c[b]);
  st.update(0, 0, n, a, r[a], c[a]);
  st.update(0, 0, n, b, r[b], c[b]);
  
  int t = 0;
  for (int i = 0; i < n; i++) {
    auto R = st.query(0, 0, n, 0, i+1);
    if (R.area() == i+1) t++;
    else i = R.area() - 2;
  }

  return t;
}

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