Submission #1307631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307631		madamadam3	Seats (IOI18_seats)	C++20	25 / 100	4094 ms	94744 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 SegTree {
  int n; vi arr; vpi st;
  SegTree() {};
  SegTree(int N, vi &Arr) {
    n = N; arr = Arr; st.assign(4*n, {INT_MIN, INT_MAX});
    build(0, 0, n);
  }

  pi combine(pi left, pi right) {
    return {max(left.first, right.first), min(left.second, right.second)};
  }

  pi build(int i, int l, int r) {
    if (l+1 == r) return st[i] = {arr[l], arr[l]};

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

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

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

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

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

int h, w;
vi r, c;
SegTree rows, cols;

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

int garea(pi R, pi C) {
  return (R.first-R.second + 1) * (C.first-C.second + 1);
}

int swap_seats(int a, int b) {
  swap(r[a], r[b]); swap(c[a], c[b]);
  rows.update(0, 0, h*w, a, r[a]), rows.update(0, 0, h*w, b, r[b]);
  cols.update(0, 0, h*w, a, c[a]), cols.update(0, 0, h*w, b, c[b]);
  
  int t = 0;
  for (int i = 0; i < h*w; i++) {
    pi R = rows.query(0, 0, h*w, 0, i+1), C = cols.query(0, 0, h*w, 0, i+1);
    if (garea(R, C) == i+1) t++;
    else i = garea(R, C) - 2;
  }

  return t;
}

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