Submission #531878

#	Time	Username	Problem	Language	Result	Execution time	Memory
531878		thiago_bastos	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	146 ms	60780 KiB

bubblesort2

#include "bubblesort2.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template<class T>
using ordered_set = tree<T ,  null_type , less<T> ,  rb_tree_tag ,  tree_order_statistics_node_update>;

using ii = pair<int, int>;
const int N = 5e5 + 100;

ordered_set<ii> bit[N];
int n;

void upd(int k, ii x) {
	for(++k; k <= n; k += k & -k) bit[k].insert(x);
}

void remove(int k, ii x) {
	for(++k; k <= n; k += k & -k) bit[k].erase(x);
}

int query(int k, ii x) {
	int cnt = 0;
	for(++k; k > 0; k -= k & -k) cnt += bit[k].order_of_key(x);
	return cnt;
}

int query(int l, int r, ii x) {
	return query(r, x) - query(l - 1, x);		
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
	int Q = X.size();
	vector<int> answer(Q);
	long long ans = 0;

	n = A.size();

	for(int i = 0; i < n; ++i) {
		ans += query(i, ii(-A[i], -1)); 
		upd(i, ii(-A[i], i));
	}

	for(int j = 0; j < Q; ++j) {
		int i = X[j];
		ans -= query(i, ii(-A[i], -1));
		ans -= n - i - query(i + 1, n - 1, ii(-A[i], n));
		remove(i, ii(-A[i], i));
		ans += query(i, ii(-V[j], -1));
		ans += n - i - query(i + 1, n - 1, ii(-V[j], n));
		upd(i, ii(-A[i], i));
		A[i] = V[j];
		answer[j] = ans;
	}

	return answer;
}

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