Submission #164038

#	Time	Username	Problem	Language	Result	Execution time	Memory
164038		dolphingarlic	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	316 ms	167672 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

indexed_set segtree[2000000];
int N;
vector<int> A;

void build(int node = 1, int l = 0, int r = N - 1) {
	if (l == r) segtree[node].insert(A[l]);
	else {
		int mid = (l + r) / 2;
		build(node * 2, l, mid);
		build(node * 2 + 1, mid + 1, r);

		for (int i : segtree[node * 2]) segtree[node].insert(i);
		for (int i : segtree[node * 2 + 1]) segtree[node].insert(i);
	}
}
int query(int a, int b, int val, int node = 1, int l = 0, int r = N - 1) {
	if (a > r || b < l) return 0;
	if (a <= l && b >= r) return segtree[node].order_of_key(val);

	int mid = (l + r) / 2;
	return query(a, b, val, node * 2, l, mid) + query(a, b, val, node * 2 + 1, mid + 1, r);
}
void update(int pos, int old, int val, int node = 1, int l = 0, int r = N - 1) {
	segtree[node].erase(segtree[node].find(old));
	segtree[node].insert(val);
	if (l != r) {
		int mid = (l + r) / 2;
		if (pos > mid) update(pos, old, val, node * 2 + 1, mid + 1, r);
		else update(pos, old, val, node * 2, l, mid);
	}
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
    int Q = X.size();
	N = A.size();
	::A = A;
    vector<int> answer(Q);

	build();
	int curr = 0;
	FOR(i, 0, N) curr += query(i, N - 1, A[i]);

    FOR(i, 0, Q) {
		curr -= query(X[i], N - 1, A[X[i]]) - query(0, X[i], A[X[i]]);
		update(X[i], A[X[i]], V[i]);
		A[X[i]] = V[i];
		curr += query(X[i], N - 1, A[X[i]]) - query(0, X[i], A[X[i]]);
		answer[i] = curr;
    }

    return answer;
}

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