Submission #70694

#	Time	Username	Problem	Language	Result	Execution time	Memory
70694		KLPP	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	7505 ms	2744 KiB

bubblesort2

#include "bubblesort2.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef long long int lld;
#define INF 1000000000
class FT{
	int arr[100000];
	int n;
	public:
	void init(int N){
		n=N;
		for(int i=0;i<=n;i++){
			arr[i]=0;
		}
	}
	int query(int prefix){
		prefix++;
		int ans=0;
		for(;prefix>0;prefix-=(prefix&(-prefix))){
			ans+=arr[prefix];
		}return ans;
	}
	void update(int pos){
		pos++;
		for(;pos<=n;pos+=(pos&(-pos))){
			arr[pos]++;
		}
	}
	void print(){
		for(int i=0;i<=n;i++){
			cout<<arr[i]<<" ";
		}cout<<endl;
	}
};
FT *F;
int compute(vector<int> v){
	int n=v.size();
	F->init(n);
	pair<int,int> arr[n];
	for(int i=0;i<n;i++){
		arr[i]=pair<int,int>(v[i],i);
	}sort(arr,arr+n);
	int prev=n-1;
	int ans=0;
	for(int i=n-1;i>-1;i--){
		if(i==0 || arr[i-1]!=arr[i]){
			for(int j=prev;j>=i;j--){
				ans=max(ans,F->query(arr[j].second));
			}
			for(int j=prev;j>=i;j--){
				F->update(arr[j].second);
			}
			prev=i-1;
		}
	}
	return ans;
}
/*class ST{
	lld segtree[1000000];
	lld maxsuffix[1000000];
	int n;
	public:
	void build(int a, int b,int node){
		maxsuffix[node]=0;
		if(a==b){
			segtree[node]=0;
			return;
		}
		int mid=(a+b)/2;
		build(a,mid,2*node);
		build(mid+1,b,2*node+1);
		segtree[node]=segtree[2*node]+segtree[2*node+1];
	}
	void init(int N){n=N;//cout<<n<<endl;
		build(0,n-1,1);
	}
	void update(int pos,lld val, int a,int b, int node){
		if(pos<a || pos>b)return;
		if(a==b){
			segtree[node]+=val;
			maxsuffix[node]=max((lld)0,segtree[node]);
			return;
		}
		int mid=(a+b)/2;
		build(a,mid,2*node);
		build(mid+1,b,2*node+1);
		segtree[node]=segtree[2*node]+segtree[2*node+1];
		maxsuffix[node]=max(maxsuffix[2*node+1],maxsuffix[2*node]+segtree[2*node+1]);
	}
	void update(int pos,lld val){
		update(pos,val,0,n-1,1);
	}
	void updatesuffix(int pos,lld val){
		update(n-1,val);
		if(pos>0){
			update(pos-1,val);
		}
	}
	lld query(){
		return maxsuffix[1];
	}
};
ST *arr[100];*/
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){F=new FT();
	if(A.size()<=8000){
	vector<int> ans;
	for(int i=0;i<X.size();i++){
		A[X[i]]=V[i];
		ans.push_back(compute(A));
	}
	return ans;
	}
	
	set<int> arr[100];
	for(int i=0;i<A.size();i++){
		arr[A[i]-1].insert(i);
		//cout<<A[i]-1<<" "<<i<<endl;
	}
	vector<int> a;
	for(int i=0;i<X.size();i++){
		arr[A[X[i]]-1].erase(X[i]);
		arr[V[i]-1].insert(X[i]);
		A[X[i]-1]=V[i];
		vector<int>H;
		for(int j=0;j<100;j++){
			if(arr[j].size()>0){
				std::set<int>::iterator it2=arr[j].begin();
				
				H.push_back(*it2);
			}
		}
		//for(int j=0;j<H.size();j++)cout<<H[j]<<endl;
		//cout<<compute(H)<<endl;
		a.push_back(compute(H));
	}//cout<<ans.size()<<endl;
	for(int i=0;i<a.size();i++)cout<<a[i]<<endl;
	return a;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:110:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:118:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<A.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:123:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:139:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++)cout<<a[i]<<endl;
              ~^~~~~~~~~

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