Submission #210917

#	Time	Username	Problem	Language	Result	Execution time	Memory
210917		casperwang	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2511 ms	62500 KiB

bubblesort2

#include <bits/stdc++.h>
#include <bubblesort2.h>
#define int long long
#define pb push_back
using namespace std;

const int MAXN = 500000;
const int K = 10000000;
int n, q;
int a[MAXN*2+5];
int cpy[MAXN*2+5];

class Seg{
private:
  int arr[MAXN*2*4+5];
  int tag[MAXN*2*4+5];
  void pull(int now) {
    arr[now] = max(arr[now*2], arr[now*2+1]);
  }
  void push(int now, int len) {
    if (!tag[now]) return;
    arr[now] += tag[now];
    if (len > 1) {
      tag[now*2  ] += tag[now];
      tag[now*2+1] += tag[now];
    }
    tag[now] = 0;
  }
public:
  void build(int now=1, int l=1, int r=MAXN*2) {
    tag[now] = 0;
    if (l == r) {
      arr[now] = 0;
      return;
    }
    int mid = (l + r) >> 1;
    build(now*2  , l, mid);
    build(now*2+1,mid+1,r);
    pull(now);
    return;
  }
  void mdy(int ml, int mr, int k, int now=1, int l=1, int r=MAXN*2) {
    push(now, r-l+1);
    if (l >= ml && r <= mr) {
      tag[now] += k;
      push(now, r-l+1);
      return;
    } else if (l > mr || r < ml) return;
    int mid = (l + r) >> 1;
    mdy(ml, mr, k, now*2  , l, mid);
    mdy(ml, mr, k, now*2+1,mid+1,r);
    pull(now);
  }
  int qry(int ql, int qr, int now=1, int l=1, int r=MAXN*2) {
    push(now, r-l+1);
    if (l >= ql && r <= qr) {
      return arr[now];
    } else if (l > qr || r < ql) return -MAXN*2;
    int mid = (l + r) >> 1, tmp = -MAXN*2;
    tmp = max(tmp, qry(ql, qr, now*2  , l, mid));
    tmp = max(tmp, qry(ql, qr, now*2+1,mid+1,r));
    pull(now);
    return tmp;
  }
} seg;

vector <signed> countScans(vector <signed> A, vector <signed> X, vector <signed> Y) {
  int n = A.size(), q = Y.size();
  for (int i = 0; i < n; i++)
    cpy[i] = A[i] * K + i;
  for (int i = 0; i < q; i++)
    cpy[i+n] = Y[i] * K + X[i];
  sort(cpy, cpy+n+q);
  seg.build();
  for (int i = 0; i < n; i++) {
    A[i] = lower_bound(cpy, cpy+n+q, A[i] * K + i) - cpy + 1;
    seg.mdy(A[i], A[i], i);
    seg.mdy(A[i]+1, n+q, -1);
  }
  vector <signed> ans;
  for (int i = 0; i < q; i++) {
    Y[i] = lower_bound(cpy, cpy+n+q, Y[i] * K + X[i]) - cpy + 1;
    seg.mdy(A[X[i]], A[X[i]], -X[i]);
    seg.mdy(A[X[i]]+1, n+q, 1);
    seg.mdy(Y[i], Y[i], X[i]);
    seg.mdy(Y[i]+1, n+q, -1);
    A[X[i]] = Y[i];
    ans.pb(seg.qry(1, MAXN*2));
  }
  return ans;
}

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