Submission #224807

#	Time	Username	Problem	Language	Result	Execution time	Memory
224807		Mamnoon_Siam	Seats (IOI18_seats)	C++17	33 / 100	786 ms	142852 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;

#define mn first
#define cnt second

ii merge(ii& a, ii& b) {
  if(a.mn < b.mn) return a;
  if(a.mn > b.mn) return b;
  return {a.mn, a.cnt + b.cnt};
}

struct node {
  int b, e;
  ii fn;
  int lz = 0;
  node *lc, *rc;
  node(int b, int e) : b(b), e(e) {}
  node(vi& a, int b, int e) : b(b), e(e) {
    if(b == e) {
      fn = {a[b], 1};
    } else {
      int m = (b + e) >> 1;
      lc = new node(a, b, m);
      rc = new node(a, m+1, e);
      fn = merge(lc -> fn, rc -> fn);
    }
  }
  void apply(int val) {
    fn.mn += val, lz += val;
  }
  void push() {
    if(b < e) {
      lc -> apply(lz);
      rc -> apply(lz);
    } lz = 0;
  }
  void update(int x, int y, int inc) {
    if(b > y or e < x) return;
    if(x <= b and e <= y) {
      apply(inc);
      return;
    }
    if(lz) push();
    lc -> update(x, y, inc);
    rc -> update(x, y, inc);
    fn = merge(lc -> fn, rc -> fn);
  }
};
typedef node* pnode;

const int maxn = 1e6 + 6;

int R[maxn], C[maxn], n, m, N;
vi a;
vi wot;
pnode root = nullptr;

int delta(int i) {
  int c = C[i], ret = 0;
  ret += (!c or wot[c-1] > i) ? 1 : -1;
  ret += (c+1 == N or wot[c+1] > i) ? 1 : -1;
  return ret;
}

void give_initial_chart(int H, int W, vector<int> RR, vector<int> CC) {
  n = H, m = W, N = n*m;
  wot.resize(N);
  for(int i = 0; i < N; ++i) {
    ::R[i] = RR[i], ::C[i] = CC[i];
    wot[::C[i]] = i;
  }
  a.resize(N);
  for(int i = 0; i < N; ++i) {
    a[i] = delta(i);
    if(i) a[i] += a[i-1];
  }
  root = new node(a, 0, N-1);
  for(int i = N-1; i >= 1; --i) {
    a[i] -= a[i-1];
  }
}

void replace(int i, int x) {
  root -> update(i, N-1, x - a[i]);
  a[i] = x;
}

int swap_seats(int p, int q) {
  swap(wot[C[p]], wot[C[q]]);
  swap(C[p], C[q]);
  p = C[p], q = C[q];
  for(int x : {p-1, p, p+1, q-1, q, q+1}) {
    if(0 <= x && x < N) {
      replace(wot[x], delta(wot[x]));
    }
  }
  return root -> fn.cnt;
}

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