Submission #164077

#	Time	Username	Problem	Language	Result	Execution time	Memory
164077		dolphingarlic	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	599 ms	215876 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<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

indexed_set segtree[2000000];
int N, cnt = 1;
vector<pair<int, 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 (auto& i : segtree[node * 2]) segtree[node].insert(i);
		for (auto& i : segtree[node * 2 + 1]) segtree[node].insert(i);
	}
}
int query(int a, int b, pair<int, 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, pair<int, int> old, pair<int, 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();
	for (int i : A) ::A.push_back({i, cnt++});
    vector<int> answer(Q);

	build();
	int curr = 0;
	FOR(i, 0, N) curr += query(i, N - 1, {::A[i].first, -1});

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

    return answer;
}

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