Submission #279893

#	Time	Username	Problem	Language	Result	Execution time	Memory
279893		ASDF123	Seats (IOI18_seats)	C++14	44 / 100	4070 ms	87524 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 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 == 1) {
    line.solution = true;
    line.give_initial_chart(H, W, R, C);
  }
  else {
    small.solution = true;
    small.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);
  }
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:202:1: warning: control reaches end of non-void function [-Wreturn-type]
  202 | }
      | ^

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