Submission #1026295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026295		Blagoj	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	310 ms	377632 KiB

bubblesort2

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

using namespace __gnu_pbds;
using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 5e5 + 100;

ll eff[mxn];

template <class type1>
using ordered_multiset = tree <type1, null_type, less_equal <type1>, rb_tree_tag, tree_order_statistics_node_update>;

struct Node {
	ordered_multiset<ll> inc, dec;
};

vector<int> A;
vector<pair<int, int>> og;

struct SGT {
	vector<Node> sgt;

	SGT(int sz) {
		sgt.resize(4 * sz);
	}

	void del(int k, ll val) {
		sgt[k].inc.erase(sgt[k].inc.lower_bound(val));
		sgt[k].dec.erase(sgt[k].dec.lower_bound(-val));
	}

	void add(int k, ll val) {
		sgt[k].inc.insert(val);
		sgt[k].dec.insert(-val);
	}

	void build(int k, int l, int r) {
		if (l == r) {
			add(k, A[l]);
			return;
		}
		int mid = (l + r) / 2;
		build(k * 2, l, mid);
		build(k * 2 + 1, mid + 1, r);
	}


	void update(int k, int l, int r, int i, ll val) {
		if (l > i || r < i) return;
		del(k, A[i]);
		add(k, val);
		if (l == r) return;
		int mid = (l + r) / 2;
		update(k * 2, l, mid, i, val);
		update(k * 2 + 1, mid + 1, r, i, val);
	}

	ll getL(int k, int l, int r, int i) {
		if (l > i) return 0;
		if (r <= i) return sgt[k].dec.order_of_key(-A[i]);
		int mid = (l + r) / 2;
		return getL(k * 2, l, mid, i) + getL(k * 2 + 1, mid + 1, r, i);
	}

	ll getR(int k, int l, int r, int i) {
		if (r < i) return 0;
		if (l >= i) return sgt[k].inc.order_of_key(A[i]);
		int mid = (l + r) / 2;
		return getR(k * 2, l, mid, i) + getR(k * 2 + 1, mid + 1, r, i);
	}
} sgt(mxn);

ll merge(int l, int r) {
	ll ans = 0;
	int mid = (l + r) / 2;
	vector<pair<ll, ll>> vl, vr;
	for (int i = l; i <= mid; i++) vl.push_back(og[i]);
	for (int i = mid + 1; i <= r; i++) vr.push_back(og[i]);
	int pl = 0, pr = 0;
	int cnt = l;
	while (pl < vl.size() && pr < vr.size()) {
		if (vl[pl].first <= vr[pr].first) og[cnt++] = vl[pl++];
		else {
			ans += vl.size() - pl;
			eff[vr[pr].second] += vl.size() - pl;
			og[cnt++] = vr[pr++];
		}
	}
	while (pl < vl.size()) og[cnt++] = vl[pl++];
	while (pr < vr.size()) og[cnt++] = vr[pr++];
	return ans;
}

ll ms(int l, int r) {
	if (l == r) return 0;
	int mid = (l + r) / 2;
	ms(l, mid);
	ms(mid + 1, r);
	return merge(l, r);
}

vector<int> countScans(vector<int> _A, vector<int> X, vector<int> V){
	A = _A;
	int Q = X.size(), N = A.size();
	for (int i = 0; i < N; i++) og.push_back({A[i], i});
	vector<int> answer(Q);
	ll ans = ms(0, N - 1);
	for (int i = 0; i < Q; i++) {
		ans -= eff[X[i]];
		A[X[i]] = V[i];
		ll get = sgt.getL(1, 0, N - 1, X[i]) + sgt.getR(1, 0, N - 1, X[i]);
		ans += get;
		eff[X[i]] = get;
		answer[i] = ans;
	}
	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'long long int merge(int, int)':
bubblesort2.cpp:88:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  while (pl < vl.size() && pr < vr.size()) {
      |         ~~~^~~~~~~~~~~
bubblesort2.cpp:88:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  while (pl < vl.size() && pr < vr.size()) {
      |                           ~~~^~~~~~~~~~~
bubblesort2.cpp:96:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  while (pl < vl.size()) og[cnt++] = vl[pl++];
      |         ~~~^~~~~~~~~~~
bubblesort2.cpp:97:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  while (pr < vr.size()) og[cnt++] = vr[pr++];
      |         ~~~^~~~~~~~~~~

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