Submission #210378

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

bubblesort2

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

const int MAXN = 500000;
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);
    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 <int> countScans(vector <int> A, vector <int> X, vector <int> Y) {
  int n = A.size(), q = Y.size();
  for (int i = 0; i < n; i++)
    cpy[i] = A[i];
  for (int i = 0; i < q; i++)
    cpy[i+n] = Y[i];
  sort(cpy, cpy+n+q);
  for (int i = 0; i < n; i++) {
    A[i] = lower_bound(cpy, cpy+n+q, A[i]) - cpy + 1;
    a[A[i]] = i;
  }
  seg.build();
  for (int i = 0; i < q; i++)
    Y[i] = lower_bound(cpy, cpy+n+q, Y[i]) - cpy + 1;
  for (int i = 0; i < n; i++)
    seg.mdy(A[i], n+q, -1);
  vector <int> 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;
}

Compilation message (stderr)

bubblesort2.cpp: In member function 'void Seg::build(int, int, int)':
bubblesort2.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
bubblesort2.cpp: In member function 'void Seg::mdy(int, int, int, int, int, int)':
bubblesort2.cpp:45:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~

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