Submission #279292

#	Time	Username	Problem	Language	Result	Execution time	Memory
279292		ASDF123	Seats (IOI18_seats)	C++14	0 / 100	461 ms	95736 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;

int pos[N], arr[N];
int n;

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];

void push(int v, int tl, int tr) {
  if (add[v] == 0) {
    return;
  }
  tree[v].mn += add[v];
  add[v + v] += add[v];
  add[v + v + 1] += add[v];
  add[v] = 0;
}

void build(int v, int tl, int tr) {
  if (tl == tr) {
    tree[v] = node(tl);
    cout << tl << ": " << tree[v].mn << " " << tree[v].cnt << endl;
    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];
}

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 (a > 0) {
    go.insert({ a - 1, a });
  }
  if (a + 1 < n) {
    go.insert({ a, a + 1 });
  }
  if (b > 0) {
    go.insert({ b - 1, b });
  }
  if (a + 1 < n) {
    go.insert({ a, a + 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;
}

//signed main() {
//  int n, m, q;
//  cin >> n >> m >> q;
//  vector <int> R, C;
//  R.resize(n * m);
//  C.resize(n * m);
//  for (int i = 0; i < n * m; i++) {
//    cin >> R[i] >> C[i];
//  }
//  give_initial_chart(n, m, R, C);
//}

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

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