Submission #71353

#	Time	Username	Problem	Language	Result	Execution time	Memory
71353		KLPP	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	4941 ms	290472 KiB

bubblesort2

#include "bubblesort2.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int lld;
typedef std::map<lld,int>::iterator mit;
#define INF 1000000000000000
class FT{
	int arr[1000000];
	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 update2(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 LP{
	lld segtree[4000000];
	lld lazy[4000000];
	int n;
	public:
	void build(int a, int b, int node){//cout<<a<<" "<<b<<endl;
		lazy[node]=0;
		if(a==b){
			segtree[node]=-INF;
			return;
		}
		int mid=(a+b)/2;
		build(a,mid,2*node);
		build(mid+1,b,2*node+1);
		segtree[node]=max(segtree[2*node],segtree[2*node+1]);
	}
	void init(int N){
		n=N;
		build(0,n-1,1);
	}
	void extend(int node){
		segtree[node]+=lazy[node];
		
			lazy[2*node]+=lazy[node];
			lazy[2*node+1]+=lazy[node];
		
		lazy[node]=0;
	}
	void update(int x, int y, lld val, int a, int b, int node){
		
		if(y<a || b<x)return;
		//cout<<x<<" "<<y<<" "<<a<<" "<<b<<" "<<node<<endl;
		if(x<=a && b<=y){
			lazy[node]+=val;
			return;
		}extend(node);
		int mid=(a+b)/2;
		update(x,y,val,a,mid,2*node);
		update(x,y,val,mid+1,b,2*node+1);
		segtree[node]=max(segtree[2*node]+lazy[2*node],segtree[2*node+1]+lazy[2*node+1]);
	}
	void Update(int x, int y, int val){
		if(x>y)return;
		update(x,y,val,0,n-1,1);
	}
	void set(int pos,lld val,int a, int b, int node){
		
		if(pos<a || pos>b)return;
		if(a==b){
			segtree[node]=val;
			lazy[node]=0;
			return;
		}extend(node);
		int mid=(a+b)/2;
		set(pos,val,a,mid,2*node);
		set(pos,val,mid+1,b,2*node+1);
		segtree[node]=max(segtree[2*node]+lazy[2*node],segtree[2*node+1]+lazy[2*node+1]);
	}
	void Set(int pos, lld val){
		set(pos,val,0,n-1,1);
	}
	lld query(){
		return segtree[1]+lazy[1];
	}
	void print(){
		for(int i=1;i<=2*n;i++){
			cout<<segtree[i]<<" "<<lazy[i]<<"   ";
		}cout<<endl;
	}
};
vector<lld> values;
int BSpos(lld x){
	int lo,hi;
	lo=-1;
	hi=values.size();
	while(hi-lo>1){
		int mid=(hi+lo)/2;
		if(values[mid]>x)hi=mid;
		else lo=mid;
	}
	if(values[lo]==x)return lo;
	return -1;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	LP *L;
	int n=A.size();
	L=new LP();
	
	vector<int> ans;
	vector<lld>a;
	vector<lld>v;
	for(int i=0;i<n;i++)a.push_back(A[i]);
	int Q=X.size();
	for(int i=0;i<Q;i++)v.push_back(V[i]);
	for(int i=0;i<n;i++)values.push_back((lld)a[i]*1000000+i);
	for(int i=0;i<Q;i++)values.push_back((lld)v[i]*1000000+X[i]);
	sort(values.begin(),values.end());
	FT *F;
	F=new FT();
	for(int i=0;i<n;i++)a[i]=a[i]*1000000+i;
	for(int i=0;i<Q;i++)v[i]=v[i]*1000000+X[i];
	F->init(n+Q);
	for(int i=0;i<n;i++){
		int pos=BSpos(a[i]);
 
		F->update(pos);
 
	}L->init(n+Q);
	for(int i=0;i<n;i++){//cout<<i<<" 1"<<endl;
		int pos=BSpos(a[i]);
		//cout<<pos<<endl;
		lld questao=F->query(pos)-1;
		//cout<<i-questao<<endl;
		L->Set(pos,i-questao);
	}
	//L->print();
	//cout<<L->query()<<endl;
	for(int i=0;i<Q;i++){//cout<<i<<" 2"<<endl;
		int pos1=BSpos(a[X[i]]);
		int pos2=BSpos(v[i]);
		F->update2(pos1);
		F->update(pos2);
		int start,end;
		
		lld query=F->query(pos2)-1;
		L->Set(pos1,-INF);
		//cout<<X[i]-query<<endl;
		L->Set(pos2,X[i]-query);
		//cout<<pos1<<" "<<pos2<<endl;
		L->Update(pos2+1,n+Q-1,-1);
		L->Update(pos1+1,n+Q-1,1);
		//cout<<L->query()<<endl;
		//L->print();
		ans.push_back(L->query());
		a[X[i]]=v[i];
	}
	return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:191:7: warning: unused variable 'start' [-Wunused-variable]
   int start,end;
       ^~~~~
bubblesort2.cpp:191:13: warning: unused variable 'end' [-Wunused-variable]
   int start,end;
             ^~~

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