Submission #842816

#	Time	Username	Problem	Language	Result	Execution time	Memory
842816		Hakiers	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	122 ms	47696 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;
const int BASE = 1 << 20;
int TREE[BASE << 1];
int LAZY[BASE << 1];
int actsetindex[BASE];
map<int, int> mapa;
priority_queue<int> Q[BASE];

void push(int v, int l, int r){
	TREE[l] += LAZY[v];
	TREE[r] += LAZY[v];
	
	LAZY[l] += LAZY[v];
	LAZY[r] += LAZY[v];
	
	LAZY[v] = 0;

}

void update(int v, int l, int r, int a, int b, int val){
	if(r < a || b < l) return;
	else if(a <= l && r <= b){
		TREE[v] += val;
		LAZY[v] += val;
	}
	else{
		int mid = (l+r)/2;
		push(v, 2*v, 2*v+1);
		update(2*v, l, mid, a, b, val);
		update(2*v+1, mid+1, r, a, b, val);
		
		TREE[v] = max(TREE[2*v], TREE[2*v+1]);
	}
}

void scale(){
	int x = 0;
	
	for(auto it = mapa.begin(); it != mapa.end(); ++it)
		it->second = x++;

}

void repair(int val){

	if(actsetindex[Q[val].top()] == val) return;
	
 	update(1, 0, BASE-1, val, val, -Q[val].top());
	
	while(Q[val].size() && actsetindex[Q[val].top()] != val)
		Q[val].pop();
		
	if(Q[val].size())
 		update(1, 0, BASE-1, val, val, Q[val].top());
}

vector<int> countScans(vector <int> A, vector<int> X, vector<int> V){
//int main(){
	//int n, q;
	
	//cin >> n >> q;
	//vector<int> A(n, 0);
	//vector<int> X(q, 0);
	//vector<int> V(q, 0);
	
	//for(int i = 0; i < (int)A.size(); i++)
		//cin >> A[i];
	//for(int i = 0; i < (int)X.size(); i++)
		//cin >> X[i];
	//for(int i = 0; i < (int)V.size(); i++)
		//cin >> V[i];
		
	
	for(auto u : A)
		mapa[u];
		
	for(auto u : V)
		mapa[u];
	scale();
	
	for(int i = 0; i < (int)A.size(); i++)
		A[i] = mapa[A[i]];
	for(int i = 0; i < (int)V.size(); i++){
		V[i] = mapa[V[i]];
		X[i]++;
	}
		
	
	
	for(int i = 0; i < (int)A.size(); i++){
		if(Q[A[i]].size())
			update(1, 0, BASE-1, A[i], A[i], -Q[A[i]].top());
		
		update(1, 0, BASE-1, A[i], A[i], i+1);
		update(1, 0, BASE-1, A[i], BASE-1, -1);
		actsetindex[i+1] = A[i];
		Q[A[i]].push(i+1);
	}
	
	//cout << max(TREE[1], 0) << endl;
	
	vector<int> res;
	
	for(int i = 0; i < (int)V.size(); i++){
		
		int idx = X[i];
		int what = actsetindex[idx];
		
		update(1, 0, BASE-1, what, BASE-1, 1);
		repair(what);
		
		
		if(Q[V[i]].size())
			update(1, 0, BASE-1, V[i], V[i], -Q[V[i]].top());
		
		
		Q[V[i]].push(idx);
		
		update(1, 0, BASE-1, V[i], V[i], Q[V[i]].top());
		update(1, 0, BASE-1, V[i], BASE-1, -1);
		actsetindex[idx] = V[i];
		
		res.push_back(max(TREE[1], 0));
		//cout << max(TREE[1], 0) << endl;	
	}
	
	return res;
	
}

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