Submission #1012179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012179		d4xn	Bubble Sort 2 (JOI18_bubblesort2)	C++17	17 / 100	9027 ms	1628 KiB

bubblesort2

#pragma GCC optimize ("Ofast")
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 8000;

int n, seg[N*4];
pair<int, int> b[N];

void update(int x, int p=1, int l=0, int r=n-1) {
  if (l == r) {
    seg[p] = 1;
    return;
  }
  int mid = (l+r) >> 1;

  if (x <= mid) update(x, p*2, l, mid);
  else update(x, p*2+1, mid+1, r);

  seg[p] = seg[p*2] + seg[p*2+1];
}

int query(int L, int R, int p=1, int l=0, int r=n-1) {
  if (L <= l && r <= R) {
    return seg[p];
  }
  int mid = (l+r) >> 1;

	int x = 0;
  if (L <= mid) x += query(L, R, p*2, l, mid);
  if (mid+1 <= R) x += query(L, R, p*2+1, mid+1, r);

	return x;
}


int solve(vector<int> a) {
	memset(seg, 0, sizeof(seg));

	for (int i = 0; i < n; i++) {
		b[i] = make_pair(a[i], i);
	}
	sort(b, b+n);

	int mx = 0;
	int R = n-1;
	for (int i = n-1; i >= 0; i--) {
		int x = query(0, b[i].second);
	
		while (R >= 0 && query(R, n-1) == n-1 - R + 1) R--;

		if (b[i].second < R) x += query(b[i].second+1, R);

		mx = max(mx, x);

		update(b[i].second);
	}
	
	return mx;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	n = A.size();
	int q = X.size();
	vector<int> ans(q);

	for (int j = 0; j < q; j++) {
		A[X[j]] = V[j];
		ans[j] = solve(A);
	}

	return ans;
}

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