Submission #97812

#	Time	Username	Problem	Language	Result	Execution time	Memory
97812		scanhex	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	449 ms	37804 KiB

bubblesort2

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

using namespace std;

const int N=500500;
int a[N];
int n;
set<pair<int,int>>all;
int sz1=100;
int sz2=0;

int memos[N];

void reb_int(){
}
struct fen1{
	vector<int>ys;
	vector<int>t;
	int n;
	void init(){
		t.resize(ys.size());
		sort(ys.begin(),ys.end());
		ys.erase(unique(ys.begin(),ys.end()),ys.end());
		n=t.size();
	}
	int get(int r){
		r=lower_bound(ys.begin(),ys.end(),r)-ys.begin();
		--r;
		int ans=0;
		for(;r>=0;r&=r+1,r--)
			ans+=t[r];
		return ans;
	}
	void ch(int x,int y){
		x=lower_bound(ys.begin(),ys.end(),x)-ys.begin();
		for(;x<n;x|=x+1)
			t[x]+=y;
	}
	int get(int l,int r){
		return get(r)-get(l);
	}
} fens[N];

void ch(int x,int y,int val){
	for(;x<N;x|=x+1)
		fens[x].ch(y,val);
}

void recalc(int i){
	int ans=i;
	int r=i-1;
//	cerr<<fens[0].t[0]<<' '<<fens[1].t[0]<<' '<<fens[1].t[1]<<'\n';
	for(;r>=0;r&=r+1,--r){
		ans-=fens[r].get(0,a[i]+1);
	}
	memos[i]=ans;
}

vector<pair<int,int>>pts;
void init_fens(){
	int ptr=0;
	for(int i=0;i<n;++i){
		while(ptr<pts.size()&&pts[ptr].first<i)++ptr;
		for(int k=i;k<n;k|=k+1)
			for(int j=ptr;j<pts.size()&&pts[j].first==i;++j)
				fens[k].ys.push_back(pts[j].second);
	}
	for(int i=0;i<n;++i){
		fens[i].init();
	}
}

int cnt=0;


void upd(int i,int coef){
	auto p=make_pair(a[i],i);
	ch(i,a[i],coef);
	if(coef==-1)
		all.erase(p);
	if(coef==1)
		all.insert(p);
	vector<int>kek;
	auto it=all.begin();
	for(int i=0;i<sz2;++i,++it){
		kek.push_back(it->second);
	}
	for(int i=0;i<sz1;++i)kek.push_back(n-i-1);
	sort(kek.begin(),kek.end());
	kek.erase(unique(kek.begin(),kek.end()),kek.end());
	for(int x:kek){
		if(i<x&&a[i]>a[x])memos[x]+=coef;
	}
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> x,std::vector<int> v){
	n=A.size();
	sz1=min(sz1,n);
	sz2=min(sz2,n);
	int q=x.size();
	copy(A.begin(),A.end(),a);
	for(int i=0;i<n;++i){
		pts.emplace_back(i,a[i]);
	}
	for(int i=0;i<q;++i)pts.emplace_back(x[i],v[i]);
	sort(pts.begin(),pts.end());
	init_fens();
	for(int i=0;i<n;++i)upd(i,1);
	vector<int>answer(q);
	for(int i=0;i<q;++i){
		upd(x[i],-1);
		a[x[i]]=v[i];
		upd(x[i],1);
		recalc(x[i]);
		for(int j=0;j<sz1;++j){
			answer[i]=max(answer[i],memos[n-j-1]);
		}
	}
	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'void init_fens()':
bubblesort2.cpp:64:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr<pts.size()&&pts[ptr].first<i)++ptr;
         ~~~^~~~~~~~~~~
bubblesort2.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=ptr;j<pts.size()&&pts[j].first==i;++j)
                  ~^~~~~~~~~~~

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