Submission #503276

#	Time	Username	Problem	Language	Result	Execution time	Memory
503276		amunduzbaev	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	372 ms	182972 KiB

bubblesort2

#include "bubblesort2.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less_equal<T>, 
rb_tree_tag, tree_order_statistics_node_update>;
 
#define ar array
//~ #define int long long

const int N = 5e5 + 5;

struct Merge_Sort_ST{
	oset<int> tree[N * 4];
	
	void erase(int i, int v, int lx = 0, int rx = N, int x = 1){
		tree[x].erase(tree[x].upper_bound(v));
		if(lx == rx) return;
		int m = (lx + rx) >> 1;
		if(i <= m) erase(i, v, lx, m, x<<1);
		else erase(i, v, m+1, rx, x<<1|1);
	}
	
	void insert(int i, int v, int lx = 0, int rx = N, int x = 1){
		tree[x].insert(v);
		if(lx == rx) return;
		int m = (lx + rx) >> 1;
		if(i <= m) insert(i, v, lx, m, x<<1);
		else insert(i, v, m+1, rx, x<<1|1);
	}
	
	int get_big(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return (int)tree[x].size() - tree[x].order_of_key(v + 1);
		int m = (lx + rx) >> 1;
		return get_big(l, r, v, lx, m, x<<1) + get_big(l, r, v, m+1, rx, x<<1|1);
	}
	
	int get_smol(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return tree[x].order_of_key(v);
		int m = (lx + rx) >> 1;
		return get_smol(l, r, v, lx, m, x<<1) + get_smol(l, r, v, m+1, rx, x<<1|1);
	}
}tt;

vector<int> countScans(vector<int> a, vector<int> in, vector<int> val){
	int n = (int)a.size(), q = (int)in.size();
	int res = 0;
	for(int i=0;i<n;i++){
		//~ cout<<tt.get_big(0, i, a[i])<<"\n";
		res += tt.get_big(0, i, a[i]);
		tt.insert(i, a[i]);
	}
	
	vector<int> rr;
	for(int j=0;j<q;j++){
		int i = in[j], v = val[j];
		res -= tt.get_big(0, i, a[i]);
		res -= tt.get_smol(i, n - 1, a[i]);
		tt.erase(i, a[i]);
		a[i] = v;
		tt.insert(i, a[i]);
		res += tt.get_big(0, i, a[i]);
		res += tt.get_smol(i, n - 1, a[i]);
		rr.push_back(res);
	} return rr;
}

/*

5 3
1 2 3 4 5
0 3
4 0
3 1

3 2 3 1 0

*/

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