Submission #842766

#	Time	Username	Problem	Language	Result	Execution time	Memory
842766		Hakiers	Bubble Sort 2 (JOI18_bubblesort2)	C++17	Compilation error	0 ms	0 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;
const int BASE = 1 << 10;
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){

	for(auto u : A)
		mapa[u];
		
	for(auto u : V)
		mapa[u];
	scale();
	
	for(int i = 0; i < A.size(); i++)
		A[i] = mapa[A[i]];
	for(int i = 0; i < V.size(); i++){
		V[i] = mapa[V[i]];
		X[i]++;
	}
		
	
	
	for(int i = 0; i < 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 < 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_bac(max(TREE[1], 0));	
	}
	
	return res;
	
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i = 0; i < A.size(); i++)
      |                 ~~^~~~~~~~~~
bubblesort2.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i = 0; i < V.size(); i++){
      |                 ~~^~~~~~~~~~
bubblesort2.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 0; i < A.size(); i++){
      |                 ~~^~~~~~~~~~
bubblesort2.cpp:90:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(int i = 0; i < V.size(); i++){
      |                 ~~^~~~~~~~~~
bubblesort2.cpp:109:7: error: 'class std::vector<int>' has no member named 'push_bac'; did you mean 'push_back'?
  109 |   res.push_bac(max(TREE[1], 0));
      |       ^~~~~~~~
      |       push_back