Submission #279594

#	Time	Username	Problem	Language	Result	Execution time	Memory
279594		ASDF123	Seats (IOI18_seats)	C++14	33 / 100	1466 ms	127636 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#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 subtask3 {
  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;
  }
} solve;

void give_initial_chart(int H, int W, vector <int> R, vector <int> C) {
  solve.give_initial_chart(H, W, R, C);
}

int swap_seats(int a, int b) {
  return solve.swap_seats(a, b);
}

//signed main() {
//  int N, M, Q;
//  cin >> N >> M >> Q;
//  vector <int> R, C;
//  vector <int> my;
//  my.resize(N * M);
//  R.resize(N * M);
//  C.resize(N * M);
//  for (int i = 0; i < M; i++) {
//    cin >> my[i];
//  }
//  for (int i = 0; i < M; i++) {
//    R[my[i]] = 0;
//    C[my[i]] = i;
//  }
//  give_initial_chart(N, M, R, C);
//
//  while (Q--) {
//    int a, b;
//    cin >> a >> b;
//    cout << swap_seats(a, b) << endl;
//  }
//}

/*
1 5 1
0 1 3 4 2
4 3
*/

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