Submission #210804

#	Time	Username	Problem	Language	Result	Execution time	Memory
210804		casperwang	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	27 ms	1400 KiB

bubblesort2

#include <bits/stdc++.h>
#include <bubblesort2.h>
#define pb push_back
#define int long long
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) {
    if (l == r) {
      arr[now] = a[l];
      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) {
      arr[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() {
    return arr[1];
  }
} 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);
  for (int i = 0; i < n; i++)
    A[i] = lower_bound(cpy, cpy+n+q, A[i] * K + i) - cpy + 1;
  for (int i = 0; i < q; i++)
    Y[i] = lower_bound(cpy, cpy+n+q, Y[i] * K + X[i]) - cpy + 1;
  for (int i = 0; i < n; i++)
    seg.mdy(A[i], n+q, -1);
  vector <signed> ans;
  for (int i = 0; i < q; i++) {
    seg.mdy(A[X[i]], n+q, 1);
    seg.mdy(Y[i], n+q, -1);
    A[X[i]] = Y[i];
    ans.pb(seg.qry());
  }
  return ans;
}

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