Submission #209469

#	Time	Username	Problem	Language	Result	Execution time	Memory
209469		TAISA_	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	2284 ms	1016 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using D=long double;
using P=pair<ll,ll>;
struct BIT{
	vector<int> bit;
	BIT(int n){
		bit.resize(++n);
	}
	void add(int k,int x){
		for(++k;k<bit.size();k+=k&-k){
			bit[k]+=x;
		}
	}
	int get(int k){
		int res=0;
		for(++k;k>0;k-=k&-k){
			res+=bit[k];
		}
		return res;
	}
};
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int n=A.size(),q=X.size();
	assert(n<=8000&&q<=8000);
	vector<int> v;
	for(int i=0;i<n;i++){
		v.eb(A[i]);
	}
	for(int i=0;i<q;i++){
		v.eb(V[i]);
	}
	sort(all(v));
	v.erase(unique(all(v)),v.end());
	int m=v.size();
	for(int i=0;i<n;i++){
		A[i]=lower_bound(all(v),A[i])-v.begin();
	}
	vector<int> res(q);
	for(int i=0;i<q;i++){
		V[i]=lower_bound(all(v),V[i])-v.begin();
		A[X[i]]=V[i];
		BIT bit(m+5);
		for(int j=0;j<n;j++){
			res[i]=max(res[i],bit.get(m+1)-bit.get(A[j]));
			bit.add(A[j],1);
		}
	}
	return res;
}

Compilation message (stderr)

bubblesort2.cpp: In member function 'void BIT::add(int, int)':
bubblesort2.cpp:15:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(++k;k<bit.size();k+=k&-k){
           ~^~~~~~~~~~~

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