Submission #1035444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035444		juicy	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	1304 ms	59568 KiB

bubblesort2

#include <bits/stdc++.h>

#include "bubblesort2.h"

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 15e5 + 5;

int SZ;
int s[4 * N], lz[4 * N], cnt[4 * N];

void app(int id, int x) {
  s[id] -= x;
  lz[id] += x;
}

void psh(int id) {
  if (lz[id]) {
    app(id * 2, lz[id]);
    app(id * 2 + 1, lz[id]);
    lz[id] = 0;
  }
}

void upd(int i, int x, int id = 1, int l = 1, int r = SZ, int rank = 0) {
  if (l == r) {
    if (x == -1) {
      s[id] = 0;
      cnt[id] = 0;
    } else {
      s[id] = x - rank;
      cnt[id] = 1;
    }
    return;
  }
  psh(id);
  int md = (l + r) / 2;
  if (i <= md) {
    app(id * 2 + 1, x == -1 ? -1 : 1);
    upd(i, x, id * 2, l, md, rank);
  } else {
    upd(i, x, id * 2 + 1, md + 1, r, rank + cnt[id * 2]);
  }
  cnt[id] = cnt[id * 2] + cnt[id * 2 + 1];
  s[id] = max(s[id * 2], s[id * 2 + 1]);
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
  int N = A.size(), Q = X.size();
  vector<array<int, 2>> comp;
  for (int i = 0; i < N; ++i) {
    comp.push_back({A[i], i});
  }
  for (int i = 0; i < Q; ++i) {
    comp.push_back({V[i], X[i]});
  }
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  SZ = comp.size();
  auto get = [&](int x, int i) {
    return lower_bound(comp.begin(), comp.end(), array<int, 2>{x, i}) - comp.begin() + 1;
  };
  for (int i = 0; i < N; ++i) {
    A[i] = get(A[i], i);
    upd(A[i], i);
  }
  auto chg = [&](int u, int x) {
    upd(A[u], -1);
    A[u] = get(x, u);
    upd(A[u], u);
  };
  vector<int> res(Q);
  for (int i = 0; i < Q; ++i) {
    chg(X[i], V[i]);
    res[i] = s[1];
  } 
  return res;
}

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