Submission #279338

#	Time	Username	Problem	Language	Result	Execution time	Memory
279338		ASDF123	Seats (IOI18_seats)	C++14	0 / 100	405 ms	95744 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];
  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);
    //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];
}

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 see() {
  for (int i = 0; i < n; i++) {
    cout << get(i, 0, 0, n - 1) << " ";
  }cout << endl;
}

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);
  
  //puts("arr");
  //for (int i = 0; i < n; i++) {
  //  cout << arr[i] << " ";
  //}cout << "\n\n";

  //puts("tree");
  //for (int i = 0; i < n; i++) {
  //  cout << get(i, 0, 0, n - 1) << " ";
  //}cout << "\n\n";


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

//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++) {
//    R[my[i]] = 0;
//    C[my[i]] = i;
//  }
//  give_initial_chart(N, M, R, C);
//  cout << "answer: " << swap_seats(0, 0) << endl;
//}

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