Submission #551907

#	Time	Username	Problem	Language	Result	Execution time	Memory
551907		QwertyPi	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	9060 ms	8652 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;
const int N = 5e5 + 5, K = 1e6 + 6;
const int INF = 1e9 + 1;
typedef pair<int, int> pii;
struct BIT{
	int bit[K + 1];
	void init(int n){
		for(int i = 1; i <= n; i++){
			bit[i] = 0;
		}
	}
	void upd(int p, int v){
		while(p <= K){
			bit[p] += v;
			p += p & -p; 
		}
	}
	int qry(int p){
		int ret = 0;
		while(p){
			ret += bit[p];
			p -= p & -p;
		}
		return ret;
	}
} bit;

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V){
	int n = A.size(), q = X.size();
	vector<int> ans(q);
	set<pair<int, int>> S; map<pii, int> M;
	for(int i = 0; i < n; i++) S.insert({A[i], i});
	for(int i = 0; i < q; i++) S.insert({V[i], X[i]});
	{ int idx = 0; for(auto i : S) M[i] = ++idx; }
	int k = S.size();
	for(int i = 0; i < n; i++) A[i] = M[{A[i], i}];
	for(int i = 0; i < q; i++) V[i] = M[{V[i], X[i]}];
	for(int i = 0; i < q; i++){
		A[X[i]] = V[i];
		bit.init(k);
		int a = 0;
		for(int j = 0; j < n; j++){
			a = max(a, j - bit.qry(A[j]));
			bit.upd(A[j], 1);
		}
		ans[i] = a;
	}
	return ans;
}

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