Submission #293443

#	Time	Username	Problem	Language	Result	Execution time	Memory
293443		rama_pang	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	3729 ms	54640 KiB

bubblesort2

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

// Number of scans = max_i{#elements greater than A[i] on the left of i}
// #elements greater than A[i] on the left of A[i] = i - #elements less
// or equal to A[i] on the left of A[i].
//
// If there is i < j and A[i] > A[j], then we will never consider i as
// a maximum candidate. Thus we can actually only find the maximum value
// of i - #elements less or equal to than A[i], since we only consider an i such
// that there is no elements lesser than A[i] on its right.
//
// We can keep a segment tree storing values (i - #elements less or equal to A[i]). 
// We can do a range update and range maximum query to find the answer.
//
// Time: O((N + Q) log N)

const int INF = 1e7;

class SegTree {
 public:
  int sz;
  vector<int> tree;
  vector<int> lazy;

  SegTree() {}
  SegTree(int sz) : sz(sz), tree(2 * sz, -INF), lazy(2 * sz) {}

  void Apply(int n, int x) {
    tree[n] += x;
    lazy[n] += x;
  }
  void Push(int n, int lc, int rc) {
    Apply(lc, lazy[n]);
    Apply(rc, lazy[n]);
    lazy[n] = 0;
  }
  void Pull(int n, int lc, int rc) {
    tree[n] = max(tree[lc], tree[rc]);
  }
  void RangeAdd(int n, int tl, int tr, int l, int r, int x) {
    if (tr < l || r < tl || tl > tr || l > r) return;
    if (l <= tl && tr <= r) return Apply(n, x);
    int md = (tl + tr) / 2;
    int lc = n + 1;
    int rc = n + 2 * (md - tl + 1);
    Push(n, lc, rc);
    RangeAdd(lc, tl, md, l, r, x);
    RangeAdd(rc, md + 1, tr, l, r, x);
    Pull(n, lc, rc);
  }
  void RangeAdd(int l, int r, int x) {
    return RangeAdd(1, 0, sz - 1, l, r, x);
  }
  void Modify(int n, int tl, int tr, int p, int x) {
    if (tl == tr) return void(tree[n] = x);
    int md = (tl + tr) / 2;
    int lc = n + 1;
    int rc = n + 2 * (md - tl + 1);
    Push(n, lc, rc);
    if (p <= md) {
      Modify(lc, tl, md, p, x);
    } else {
      Modify(rc, md + 1, tr, p, x);
    }
    Pull(n, lc, rc);
  }
  void Modify(int p, int x) {
    return Modify(1, 0, sz - 1, p, x);
  }
  int Query() {
    return tree[1];
  }
};

class Fenwick {
 public:
  int sz;
  vector<int> tree;

  Fenwick() {}
  Fenwick(int sz) : sz(sz), tree(sz) {}

  void Update(int p, int x) {
    for (int i = p; i < sz; i |= i + 1) {
      tree[i] += x;
    }
  }
  int Query(int p) {
    int res = 0;
    for (int i = p; i > 0; i &= i - 1) {
      res += tree[i - 1];
    }
    return res;
  }
};

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
  int N = A.size();
  int Q = X.size();

  vector<pair<int, int>> coords;
  for (int i = 0; i < N; i++) {
    coords.emplace_back(A[i], i);
  }
  for (int i = 0; i < Q; i++) {
    coords.emplace_back(V[i], X[i]);
  }
  sort(begin(coords), end(coords));
  coords.resize(unique(begin(coords), end(coords)) - begin(coords));
  auto Position = [&](int x, int y) -> int {
    return lower_bound(begin(coords), end(coords), make_pair(x, y)) - begin(coords);
  };

  SegTree seg(coords.size());
  Fenwick active(coords.size());
  for (int i = 0; i < N; i++) {
    active.Update(Position(A[i], i), 1);
  }
  for (int i = 0; i < N; i++) {
    seg.Modify(Position(A[i], i), i - active.Query(Position(A[i], i)));
  }

  vector<int> answer(Q);
  for (int i = 0; i < Q; i++) {
    seg.RangeAdd(Position(A[X[i]], X[i]) + 1, int(coords.size()) - 1, +1);
    seg.Modify(Position(A[X[i]], X[i]), -INF);
    active.Update(Position(A[X[i]], X[i]), -1);
    A[X[i]] = V[i];
    active.Update(Position(A[X[i]], X[i]), +1);
    seg.RangeAdd(Position(A[X[i]], X[i]) + 1, int(coords.size()) - 1, -1);
    seg.Modify(Position(A[X[i]], X[i]), X[i] - active.Query(Position(A[X[i]], X[i])));
    answer[i] = seg.Query();
  }
  return answer;
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40