oj.uz

Submission #531878

# Submission time Handle Problem Language Result Execution time Memory
531878 2022-03-01T19:06:36 Z thiago_bastos Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 146 ms 60780 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 47500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 47500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 60780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 47500 KB Output isn't correct
2 Halted 0 ms 0 KB -