Submission #539131

#	Time	Username	Problem	Language	Result	Execution time	Memory
539131		LucaDantas	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	9085 ms	4308 KiB

bubblesort2

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

constexpr int maxn = 5e5+10;

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();
	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:33:25: warning: unused variable 'N' [-Wunused-variable]
   33 |  int Q = (int)X.size(), N = (int)A.size();
      |                         ^

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