Submission #1089575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089575		VMaksimoski008	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9041 ms	2776 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int maxn = 5e5 + 5;

struct BIT {
	int n;
	vector<int> tree;

	BIT(int _n) : n(_n+10), tree(_n+60) {}

	void update(int p) {
		for(p++; p<n; p+=p&-p) tree[p]++;
	}

	int query(int p) {
		int ans = 0;
		for(p++; p>0; p-=p&-p) ans += tree[p];
		return ans;
	}

	void clear() { for(int &x : tree) x = 0; }
};

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

	vector<int> ans(q);
	BIT bit(n);
	for(int it=0; it<q; it++) {
		A[X[it]] = V[it];
		bit.clear();
		vector<pii> vec;
		for(int i=0; i<n; i++) vec.push_back({ A[i], i });
		sort(vec.rbegin(), vec.rend());
		for(auto &[val, id] : vec) {
			ans[it] = max(ans[it], bit.query(id));
			bit.update(id);
		}
	}

	return ans;
}

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