Submission #1109763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109763		VinhLuu	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	1631 ms	87280 KiB

bubblesort2

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

const int N = 1e6 + 5;
const int oo = -1e9;

int n, m, q, a[N], _x[N], _y[N], kq[N], pos[N];

int st[N << 2], lz[N << 2], le[N], ri[N];

void build(int i,int l,int r){
  if(l == r){
    st[i] = oo;
    return;
  }
  int mid = (l + r) / 2;
  build(i << 1, l, mid);
  build(i << 1|1, mid + 1, r);
  st[i] = max(st[i << 1], st[i << 1|1]);
}

void dolz(int i){
  if(!lz[i]) return;
  int x = lz[i]; lz[i] = 0;
  lz[i << 1] += x;
  lz[i << 1|1] += x;
  st[i << 1] += x;
  st[i << 1|1] += x;
}

void update(int i,int l,int r,int u,int v,int x){
  if(l > r || r < u || v < l) return;
  if(u <= l && r <= v){
    st[i] += x;
    lz[i] += x;
    return;
  }
  dolz(i);
  int mid = (l + r) / 2;
  update(i << 1, l, mid, u, v, x);
  update(i << 1|1, mid + 1, r, u, v, x);
  st[i] = max(st[i << 1], st[i << 1|1]);
}

void change(int i,int l,int r,int u,int val){
  if(l > r || r < u || u < l) return;
  if(l == r){
    st[i] = val;
    lz[i] = 0;
    return;
  }
  dolz(i);
  int mid = (l + r) / 2;
  change(i << 1, l, mid, u, val);
  change(i << 1|1, mid + 1, r, u, val);
  st[i] = max(st[i << 1], st[i << 1|1]);
}

int b[N], T[N];

void inc(int x,int val){
  for(int i = x; i <= m; i += i & (-i)) T[i] += val;
}

int query(int x){
  int ret = 0;
  for(int i = x; i; i -= i & (-i)) ret += T[i];
  return ret;
}

int c[N];

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
  n = A.size();
  for(int i = 0; i < n; i ++){
    a[i + 1] = A[i];
    c[++m] = i + 1;
  }

  q = X.size();

  for(int k = 0; k < q; k ++){
    _x[k + 1] = X[k] + 1, _y[k + 1] = V[k];
    c[++m] = n + k + 1;
    a[n + k + 1] = _y[k + 1];
  }

  sort(c + 1, c + m + 1, [&](int x,int y){return a[x] < a[y];});

  int last = 1;

  for(int i = 1; i <= m; i ++){
    if(a[c[i]] != a[c[i - 1]]) last = i;
    le[i] = last;
    pos[c[i]] = i;
  }
  last = m;
  for(int i = m; i >= 1; i --){
    if(a[c[i]] != a[c[i + 1]]) last = i;
    ri[i] = last;
  }

//  for(int i = 1; i <= m; i ++) cerr << i << " " << pos[i] << " " << le[pos[i]] << " " << ri[pos[i]] << " k\n";

  build(1, 1, m);
  for(int i = 1; i <= n; i ++){
    change(1, 1, m, pos[i], i);
    inc(pos[i], 1);
  }
  for(int i = 1; i <= n; i ++){
    update(1, 1, m, le[pos[i]], m, -1);
    b[i] = i;
  }

  for(int k = 1; k <= q; k ++){
    int x = _x[k];
    int y = _y[k];
    int tmp = pos[n + k];
    update(1, 1, m, le[pos[b[x]]], m, +1);
    change(1, 1, m, pos[b[x]], oo);
    inc(pos[b[x]], -1);
    inc(tmp, 1);
    update(1, 1, m, le[tmp], m, -1);
    change(1, 1, m, tmp, x - query(ri[tmp]));

    b[x] = n + k;
    kq[k] = st[1];
  }

	std::vector<int> answer(q);
	for(int j = 0; j < q; j ++) {
		answer[j] = kq[j + 1];
	}
	return answer;
}

//#define LOCAL

#ifdef LOCAL

int _n, _q;

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

	cin >> _n >> _q;

	std::vector<int> A(_n);
  for(int i = 0; i < _n; i ++)
    cin >> A[i];

	std::vector<int> X(_q),V(_q);
	for(int j = 0; j < _q ; j++){
		cin >> X[j] >> V[j];
	}


	std::vector<int> res=countScans(A,X,V);

	for(int j=0;j<int(res.size());j++)
		cout << res[j] << "\n";
}

/*
4 2
1 2 3 4
0 3
2 1
*/

#endif // LOCAL

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:119:9: warning: unused variable 'y' [-Wunused-variable]
  119 |     int y = _y[k];
      |         ^

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