Submission #280091

#	Time	Username	Problem	Language	Result	Execution time	Memory
280091		ASDF123	Seats (IOI18_seats)	C++14	44 / 100	4010 ms	96480 KiB

seats

/*
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░▄▄███▄▄▄░▄▄██▄░░░░░░░
░░░░░░░░░██▀███████████████▀▀▄█░░░░░░
░░░░░░░░█▀▄▀▀▄██████████████▄░░█░░░░░
░░░░░░░█▀▀░▄██████████████▄█▀░░▀▄░░░░
░░░░░▄▀░░░▀▀▄████████████████▄░░░█░░░
░░░░░▀░░░░▄███▀░░███▄████░████░░░░▀▄░
░░░▄▀░░░░▄████░░▀▀░▀░░░░░░██░▀▄░░░░▀▄
░▄▀░░░░░▄▀▀██▀░░░░░▄░░▀▄░░██░░░▀▄░░░░
█░░░░░█▀░░░██▄░░░░░▀▀█▀░░░█░░░░░░█░░░
█░░░▄▀░░░░░░██░░░░░▀██▀░░█▀▄░░░░░░▀▀▀
▀▀▀▀░▄▄▄▄▄▄▀▀░█░░░░░░░░░▄█░░█▀▀▀▀▀█░░
░░░░█░░░▀▀░░░░░░▀▄░░░▄▄██░░░█░░░░░▀▄░
░░░░█░░░░░░░░░░░░█▄▀▀▀▀▀█░░░█░░░░░░█░
░░░░▀░░░░░░░░░░░░░▀░░░░▀░░░░▀░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░
*/
#include "seats.h"
#include <bits/stdc++.h>
#define chkmax(a, b) a = max(a, (b))
#define chkmin(a, b) a = min(a, (b))

#define fr first
#define sc second
#define pii pair<int, int>
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;

const int N = (int)1e6 + 6;
const int INF = 0x3f3f3f3f;

struct mnmx {
  int mn, mx;
  mnmx() {
    mn = INF, mx = -INF;
  }
};

int get(mnmx a, mnmx b) {
  return (a.mx - a.mn + 1) * (b.mx - b.mn + 1);
}

struct subtask12 {
  vector <int> posy, posx;
  vector <int> id;
  int n, m;
  
  bool solution = false;

  void give_initial_chart(int H, int W, vector <int> R, vector <int> C) {
    posy.resize(H * W);
    posx.resize(H * W);
    n = H, m = W;
    for (int i = 0; i < H * W; i++) {
      posy[i] = R[i];
      posx[i] = C[i];
    }
  }
  int swap_seats(int a, int b) {
    swap(posy[a], posy[b]);
    swap(posx[a], posx[b]);
    mnmx R, C;
    int ans = 0;
    for (int i = 0; i < n * m; i++) {
      chkmin(R.mn, posy[i]);
      chkmax(R.mx, posy[i]);
      chkmin(C.mn, posx[i]);
      chkmax(C.mx, posx[i]);
      if (get(R, C) == i + 1) {
        ans++;
      }
    }
    return ans;
  }
} small;

struct subtask3 {
  /*
  создать дерево отрезков чтобы отвечать на запросы min max y/x
  */
  vector <int> y, x;
  struct node {
    int mn, mx;
    node(int x) {
      mn = mx = x;
    }
    node() {
      mn = INF, mx = -INF;
    }
    node operator + (const node& other) {
      node res;
      res.mn = min(mn, other.mn);
      res.mx = max(mx, other.mx);
      return res;
    }
  };

  struct Tree {
    node* tree;
    Tree (int Area) {
      tree = (node*)malloc(Area * sizeof (node));
    }
    Tree() {
      tree = nullptr;
    }
    void build(int v, int tl, int tr, vector <int> &arr) { // 0 индексация
      if (tl == tr) {
        tree[v] = node(arr[tl]);
        return;
      }
      int mid = (tl + tr) >> 1;
      build(v * 2 + 1, tl, mid, arr);
      build(v * 2 + 2, mid + 1, tr, arr);
      tree[v] = tree[v * 2 + 1] + tree[v * 2 + 2];
    }
    void upd(int pos, int val, int v, int tl, int tr) {
      if (tl == tr) {
        tree[v] = node(val);
        return;
      }
      int mid = (tl + tr) >> 1;
      if (pos <= mid) {
        upd(pos, val, v * 2 + 1, tl, mid);
      }
      else {
        upd(pos, val, v * 2 + 2, mid + 1, tr);
      }
      tree[v] = tree[v * 2 + 1] + tree[v * 2 + 2];
    }
    node get(int l, int r, int v, int tl, int tr) {
      if (l <= tl && tr <= r) {
        return tree[v];
      }
      if (l > tr || tl > r) {
        return node();
      }
      int mid = (tl + tr) >> 1;
      return get(l, r, v * 2 + 1, tl, mid) + get(l, r, v * 2 + 2, mid + 1, tr);
    }
  };
  bool solution = false;
  Tree row, col;
  int Area;
  
  int ourH, ourW;

  void give_initial_chart(int H, int W, vector <int> R, vector <int> C) {
    assert(H == 1000 && W == 1000);
    y.resize(H * W);
    x.resize(H * W);
    Area = H * W;
    ourH = H;
    ourW = W;
    for (int i = 0; i < Area; i++) {
      y[i] = R[i], x[i] = C[i];
    }
    row = Tree(Area * 3);
    col = Tree(Area * 3);
    row.build(0, 0, Area - 1, y);
    col.build(0, 0, Area - 1, x);
  }
  int swap_seats(int a, int b) {
    int pos = 0, ans = 0;
    swap(x[a], x[b]);
    swap(y[a], y[b]);
    row.upd(a, y[a], 0, 0, Area - 1);
    col.upd(a, x[a], 0, 0, Area - 1);
    row.upd(b, y[b], 0, 0, Area - 1);
    col.upd(b, x[b], 0, 0, Area - 1);
    while (pos < Area) { 
      node R = row.get(0, pos, 0, 0, Area - 1);
      node C = col.get(0, pos, 0, 0, Area - 1);
      int rectangle = (R.mx - R.mn + 1) * (C.mx - C.mn + 1);
      if (rectangle == pos + 1) {
        ans++, pos++;
      }
      else {
        pos = rectangle - 1;
      }
    }
    return ans;
  }
} a_plus_b;

struct subtask5 {
  bool solution = false;
  struct node {
    int mn, cnt;
    node(int x) {
      mn = x, cnt = 1;
    }
    node() {
      mn = INF, cnt = 0;
    }
    node operator + (const node& other) {
      node res;
      res.mn = min(mn, other.mn);
      res.cnt = 0;
      if (res.mn == mn) res.cnt += cnt;
      if (res.mn == other.mn) res.cnt += other.cnt;
      return res;
    }
  };

  node tree[4 * N];
  int add[4 * N];
  int pos[N], arr[N];
  int n;
  
  void push(int v, int tl, int tr) {
    if (add[v] == 0) {
      return;
    }
    tree[v].mn += add[v];
    if (tl != tr) {
      add[v + v + 1] += add[v];
      add[v + v + 2] += add[v];
    }
    add[v] = 0;
  }

  void build(int v, int tl, int tr) {
    if (tl == tr) {
      tree[v] = node(tl);
      return;
    }
    int mid = (tl + tr) >> 1;
    build(v + v + 1, tl, mid);
    build(v + v + 2, mid + 1, tr);
    tree[v] = tree[v + v + 1] + tree[v + v + 2];
  }

  void upd(int ql, int qr, int val, int v, int tl, int tr) {
    push(v, tl, tr);
    if (ql > tr || tl > qr) {
      return;
    }
    if (ql <= tl && tr <= qr) {
      add[v] += val;
      push(v, tl, tr);
      return;
    }
    int mid = (tl + tr) >> 1;
    upd(ql, qr, val, v + v + 1, tl, mid);
    upd(ql, qr, val, v + v + 2, mid + 1, tr);
    tree[v] = tree[v + v + 1] + tree[v + v + 2];
  }
  int get(int pos, int v, int tl, int tr) {
    push(v, tl, tr);
    if (tl == tr) {
      return tree[v].mn;
    }
    int mid = (tl + tr) >> 1;
    if (pos <= mid) {
      return get(pos, v + v + 1, tl, mid);
    }
    else {
      return get(pos, v + v + 2, mid + 1, tr);
    }
  }
  void give_initial_chart(int H, int W, vector <int> R, vector <int> C) {
    assert(H == 1);
    n = W;

    for (int i = 0; i < n; i++) {
      pos[i] = C[i];
    }

    for (int i = 0; i < n; i++) {
      arr[pos[i]] = i;
    }

    build(0, 0, n - 1);

    for (int i = 0; i + 1 < n; i++) {
      int mx = max(arr[i], arr[i + 1]);
      upd(mx, n - 1, -1, 0, 0, n - 1);
    }
  }
  int swap_seats(int a, int b) {
    set <pair<int, int>> go;
    if (pos[a] > 0) {
      go.insert({ pos[a] - 1, pos[a] });
    }
    if (pos[a] + 1 < n) {
      go.insert({ pos[a], pos[a] + 1 });
    }
    if (pos[b] > 0) {
      go.insert({ pos[b] - 1, pos[b] });
    }
    if (pos[b] + 1 < n) {
      go.insert({ pos[b], pos[b] + 1 });
    }
    for (pii pr : go) {
      int mx = max(arr[pr.fr], arr[pr.sc]);
      upd(mx, n - 1, 1, 0, 0, n - 1);
    }
    swap(arr[pos[a]], arr[pos[b]]);
    swap(pos[a], pos[b]);
    for (pii pr : go) {
      int mx = max(arr[pr.fr], arr[pr.sc]);
      upd(mx, n - 1, -1, 0, 0, n - 1);
    }
    return tree[0].cnt;
  }
} line;

void give_initial_chart(int H, int W, vector <int> R, vector <int> C) {
  if (H * W <= 10000) {
    small.solution = true;
    small.give_initial_chart(H, W, R, C);
  }
  else if (H == 1) {
    line.solution = true;
    line.give_initial_chart(H, W, R, C);
  }
  else if (H <= 1000 && W <= 1000) {
    a_plus_b.solution = true;
    a_plus_b.give_initial_chart(H, W, R, C);
  }
}

int swap_seats(int a, int b) {
  if (line.solution) {
    return line.swap_seats(a, b);
  }
  if (small.solution) {
    return small.swap_seats(a, b);
  }
  if (a_plus_b.solution) {
    return a_plus_b.swap_seats(a, b);
  }
  assert(false);
}

/*signed main() {

}*/

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