Submission #1223813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223813		madamadam3	Seats (IOI18_seats)	C++20	20 / 100	4090 ms	164856 KiB

seats

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

using namespace std;

using vi = vector<int>;

const int NULLV = -100;

struct Node {
  int C1, C2, R1, R2, area;

  Node() : C1(NULLV), C2(NULLV), R1(NULLV), R2(NULLV), area(0) {};
  Node(int row, int col) : C1(col), C2(col), R1(row), R2(row), area(1) {};
  Node(Node left, Node right) {
    if (left.C1 == NULLV && right.C1 == NULLV) C1 = NULLV, C2 = NULLV, R1 = NULLV, R2 = NULLV, area = 0;
    else if (left.C1 == NULLV) C1 = right.C1, C2 = right.C2, R1 = right.R1, R2 = right.R2, area = right.area;
    else if (right.C1 == NULLV) C1 = left.C1, C2 = left.C2, R1 = left.R1, R2 = left.R2, area = left.area;
    else {
      C1 = min({left.C1, left.C2, right.C1, right.C2});
      C2 = max({left.C1, left.C2, right.C1, right.C2});
      R1 = min({left.R1, left.R2, right.R1, right.R2});
      R2 = max({left.R1, left.R2, right.R1, right.R2});

      area = (C2 - C1 + 1) * (R2 - R1 + 1);
    }
  }
};

struct SegTree {
  int n; vector<Node> st;
  vi rows, cols;

  SegTree() : n(0) {};

  SegTree(int w, int h, vi &Rows, vi &Cols) {
    n = w*h;
    rows = Rows;
    cols = Cols;

    st.assign(4*n, Node());

    build(0, 0, n);
  }

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

  Node update(int i, int l, int r, int k, int vrow, int vcol) {
    if (!(l <= k && k < r)) return st[i];
    if (l + 1 == r) return st[i] = Node(vrow, vcol);

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

  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 prefix_query(int r) {
    return query(0, 0, n, 0, r+1);
  }

  void swap_nodes(int a, int b) {
    swap(cols[a], cols[b]);
    swap(rows[a], rows[b]);

    update(0, 0, n, a, rows[a], cols[a]);
    update(0, 0, n, b, rows[b], cols[b]);
  }
};

struct LazySegTree {
  int n; vi st, lazy;

  LazySegTree() : n(0) {};

  LazySegTree(int w, int h) {
    n = w*h;
    st.assign(4*n, 0);
    lazy.assign(4*n, 0);
  }

  void apply(int i, int l, int r, int op) {
    if (op == 0) return;

    int length = r - l;
    lazy[i] = op;

    if (op == 1) st[i] = 0;
    else st[i] = length;
  }

  void push_down(int i, int l, int r) {
    int m = l + (r - l) / 2;
    apply(2*i+1, l, m, lazy[i]);
    apply(2*i+2, m, r, lazy[i]);

    lazy[i] = 0;
  }

  int range_assign(int i, int l, int r, int ql, int qr, int v) {
    if (r <= ql || qr <= l) return st[i];
    if (ql <= l && r <= qr) {
      apply(i, l, r, v == 0 ? 1 : 2);
      return st[i];
    }

    push_down(i, l, r);
    int m = l + (r - l) / 2;
    return st[i] = range_assign(2*i+1, l, m, ql, qr, v) + range_assign(2*i+2, m, r, ql, qr, v);
  }

  int query(int i, int l, int r, int ql, int qr) {
    if (r <= ql || qr <= l) return 0;
    if (ql <= l && r <= qr) return st[i];
    
    push_down(i, l, r);
    int m = l + (r - l) / 2;
    return query(2*i+1, l, m, ql, qr) + query(2*i+2, m, r, ql, qr);
  }

  void set_zero(int l, int r) {
    range_assign(0, 0, n, l, r+1, 0);
  }

  void set_one(int i) {
    range_assign(0, 0, n, i, i+1, 1);
  }

  int get_beautiful() {
    return query(0, 0, n, 0, n);
  }
};

struct MaxST {
  int n; vi st, arr;

  MaxST() : n(0) {};

  MaxST(int w, int h, vi &row) {
    n = w*h;
    arr = row;

    st.assign(4*n, INT_MIN);
    build(0, 0, n);
  }

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

  int update(int i, int l, int r, int k, int v) {
    if (!(l <= k && k < r)) return st[i];
    if (l + 1 == r) return st[i] = arr[k] = v;

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

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

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

  int query(int l, int r) {
    return query(0, 0, n, l, r+1);
  }

  void swap_nodes(int a, int b) {
    swap(arr[a], arr[b]);

    update(0, 0, n, a, arr[a]);
    update(0, 0, n, b, arr[b]);
  }
};

int h, w;
vi rows, cols;
SegTree st;
LazySegTree prev_ans;
MaxST mst;

void give_initial_chart(int H, int W, vi R, vi C) {
  h = H; w = W;
  rows = R; cols = C;

  st = SegTree(w, h, rows, cols);
  prev_ans = LazySegTree(w, h);
  if (H == 1) {
    vi arr(h*w);
    for (int i = 0; i < h*w; i++) arr[cols[i]] = i;
    mst = MaxST(w, h, arr);
  }
}

int queries = 0;
int swap_seats(int a, int b) {
  if (a > b) swap(a, b);
  queries++;

  swap(rows[a], rows[b]);
  swap(cols[a], cols[b]);

  st.swap_nodes(a, b);
  if (h == 1) mst.swap_nodes(a, b);

  // for (int i = 0; i < w; i++) for (int k = 0; k < w; k++) if (cols[k] == i) cout << k << " ";
  // cout << "\n";

  int start = a, end = b+1;
  if (queries <= 1) start = 0, end = h*w;
  prev_ans.set_zero(start, end - 1);

  for (int i = start; i < end;) {
    Node cur = st.prefix_query(i);
    // cout << "i = " << i << " (R1, R2) = (" << cur.R1 << ", " << cur.R2 << ") (C1, C2) = " << cur.C1 << ", " << cur.C2 << ") Area = " << cur.area << "\n";
    if (cur.area == i+1) {
      prev_ans.set_one(i);
      // cout << "Beautiful array for: " << i << "\n";
      i++;
    } else {
      // cout << i << " wasn't beautiful. Jumping to i = " << cur.area << "\n";
      i = cur.area - 1;
      if (h == 1) {
        i = max(i, mst.query(cur.C1, cur.C2)-1);
      }
    }
  }

  return prev_ans.get_beautiful();
}

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