Submission #539135

#	Time	Username	Problem	Language	Result	Execution time	Memory
539135		LucaDantas	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9004 ms	5356 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;

constexpr int maxn = 1e6+10; // subtasks brutao, mudar

struct BIT {
	int bit[maxn];
	void upd(int x, int v) {
		for(; x > 0; x -= x&-x)
			bit[x] += v;
	}
	int query(int x) {
		int ans = 0;
		for(; x < maxn; x += x&-x)
			ans += bit[x];
		return ans;
	}
	void clear() { memset(bit, 0, sizeof bit); }
} bit;

// fazer o brutao pra checar se essa ideia ta certo e se eu codo ela pra full

int calc(const vector<int>& A) {
	int ans = 0;
	bit.clear();
	for(int i = 0; i < (int)A.size(); i++) {
		ans = max(ans, bit.query(A[i]+1)), bit.upd(A[i], 1);
	}
	return ans;
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int Q = (int)X.size(), N = (int)A.size();
	
	map<int,int> mp;
	for(int x : A)
		mp[x] = 0;
	for(int x : V)
		mp[x] = 0;

	int coord = 0;
	for(auto& it : mp)
		it.second = ++coord;

	for(int& x : A)
		x = mp[x];
	for(int& x : V)
		x = mp[x];

	std::vector<int> answer(Q);
	for(int q = 0; q < Q; q++) {
		A[X[q]] = V[q];
		answer[q] = calc(A);
	}
	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:34:25: warning: unused variable 'N' [-Wunused-variable]
   34 |  int Q = (int)X.size(), N = (int)A.size();
      |                         ^

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