Submission #282772

#	Time	Username	Problem	Language	Result	Execution time	Memory
282772		Haunted_Cpp	Seats (IOI18_seats)	C++17	33 / 100	634 ms	95612 KiB

seats

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

int H, W;
vector<int> R, C, diff, elem;

class SegmentTree {
private:
  struct Node {
    int pre_mn, pre_cnt, sum;
    Node() {
      pre_mn = pre_cnt = sum = 0;
    }
    void merge(Node l, Node r) {
      pre_mn = l.pre_mn;
      pre_cnt = l.pre_cnt;
      if (l.sum + r.pre_mn == pre_mn) {
        pre_cnt += r.pre_cnt;
      }
      if (l.sum + r.pre_mn < pre_mn) {
        pre_mn = l.sum + r.pre_mn;
        pre_cnt = r.pre_cnt;
      }
      sum = l.sum + r.sum;
    }
  };
  vector<Node> seg;
  const int LO, HI;
  void build(int l, int r, int node, const vector<int> &arr) {
    if (l == r) {
      seg[node].pre_mn = seg[node].sum = arr[l];
      seg[node].pre_cnt = 1;
      return;
    }
    const int mid = l + (r - l) / 2;
    build(l, mid, 2 * node + 1, arr);
    build(mid + 1, r, 2 * node + 2, arr);
    seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
  }
  void modify(int where, int delta, int l, int r, int node) {
    if (l > where || r < where) return;
    if (l == where && r == where) {
      seg[node].pre_mn = seg[node].sum = delta;
      seg[node].pre_cnt = 1;
      return;
    }
    const int mid = l + (r - l) / 2;
    modify(where, delta, l, mid, 2 * node + 1);
    modify(where, delta, mid + 1, r, 2 * node + 2);
    seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
  }
public:
  SegmentTree(const vector<int> &arr) : LO(0), HI((int)arr.size() - 1){
    seg.clear();
    seg.resize(4 * arr.size());
    build(LO, HI, 0, arr);
  }
  int get_ans() {
    return seg[0].pre_cnt;
  }
  void modify(int where, int delta) {
    modify(where, delta, LO, HI, 0);
  }
};

SegmentTree *seg;

int calc_delta(int where) {
  int s = 0;
  s += ( (where == 0) || (elem[where - 1] > elem[where]) ? 1 : -1);
  s += ( (where == W - 1) || (elem[where + 1] > elem[where]) ? 1 : -1);
  return s;
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  ::H = H; ::W = W;
  ::R = R; ::C = C;
  diff.resize(W);
  elem.resize(W);
  for (int i = 0; i < W; i++) {
    elem[C[i]] = i;
  }
  for (int i = 0; i < W; i++) {
    diff[i] = calc_delta(C[i]);
  }
  seg = new SegmentTree(diff);
}

int swap_seats(int a, int b) {
  swap(elem[C[a]], elem[C[b]]);
  swap(C[a], C[b]);
  if (C[a] - 1 >= 0) seg -> modify(elem[C[a] - 1], calc_delta(C[a] - 1));
  seg -> modify(a, calc_delta(C[a]));
  if (C[a] + 1 < W) seg -> modify(elem[C[a] + 1], calc_delta(C[a] + 1));
  if (C[b] - 1 >= 0) seg -> modify(elem[C[b] - 1], calc_delta(C[b] - 1));
  seg -> modify(b, calc_delta(C[b]));
  if (C[b] + 1 < W) seg -> modify(elem[C[b] + 1], calc_delta(C[b] + 1));
  return seg -> get_ans();
}

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