Submission #58928

#	Time	Username	Problem	Language	Result	Execution time	Memory
58928		khohko	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	6615 ms	204384 KiB

bubblesort2

#include<bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define ll int
#define fr first
#define sc second
#define pb push_back
#define ARRS ((ll)(1e6+100))
#define MAX ((ll)(1e9+100))

ll fw[ARRS+100];

void add(ll i,ll x){
	i=ARRS-i;
	while(i<=ARRS+10){
		fw[i]+=x;
		i+=i&-i;
	}
}

ll quer(ll i){
	i=ARRS-i;
	ll p=0;
	while(i>0){
		p+=fw[i];
		i-=i&-i;
	}
	return p;
}

ll wl,wr,wx,wi;

struct node{
	node *L,*R;
	int x,s;
	node(){
		L=R=NULL;
		s=0;
		x=-MAX;
	}
	void updt(){
		x=-MAX;
		if(L)x=max(x,L->x);
		if(R)x=max(x,R->x);
	}
	void shep(ll y){
		s+=y;
		x+=y;
	}
	void shplit(){
		if(!L)L=new node();
		if(!R)R=new node();
		L->shep(s);
		R->shep(s);
		s=0;
	}
};

void updt(ll l,ll r,node *& x){
	if(wr<l||r-1<wl)return;
	if(!x)x=new node();
	if(wl<=l&&r-1<=wr){
		x->shep(wx);
		return;
	}
	x->shplit();
	updt(l,l+r>>1,x->L);
	updt(l+r>>1,r,x->R);
	x->updt();
}

void updt1(ll l,ll r,node *& x){
	if(wr<l||r-1<wl)return;
	if(!x)x=new node();
	if(wl<=l&&r-1<=wr){
		x->x=wx;
		x->s=0;
		return;
	}
	x->shplit();
	updt1(l,l+r>>1,x->L);
	updt1(l+r>>1,r,x->R);
	x->updt();
}

set<ll> mp[ARRS];

node *rt=NULL;

void up(ll x){
	if(mp[x].size()){
		wl=wr=x;
		wx=-(*mp[x].begin())+quer(x+1);
//		cout<<wl<<" "<<wx<<" "<<x<<" "<<(-*mp[x].begin())<<endl;
		updt1(-MAX,MAX,rt);
	}
	else {
		wl=wr=x;
		wx=-MAX;
		updt1(-MAX,MAX,rt);
	}
}

ll a[ARRS],n;
map<ll,ll> em;

void quer(ll i,ll x){

	mp[a[i]].erase(n-i-1);
	mp[x].insert(n-i-1);

	add(a[i],-1);
	add(x,1);

	up(x);
	up(a[i]);
	if(a[i]<=x){
		wl=a[i]+1;
		wr=x-1;
		wx=1;
	}
	else {
		wl=x+1;
		wr=a[i]-1;
		wx=-1;
	}
	updt(-MAX,MAX,rt);
	a[i]=x;
}


vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	n=A.size();
	ll q=X.size();
	vector<int> PAS;
	vector<int> b;
	for(auto x:A)
		b.pb(x);
	for(auto x:V)
		b.pb(x);
	sort(b.begin(),b.end());
	ll C=1;
	for(int i=0; i<b.size(); i++){
		if(b[i]!=b[i-1]||!i)
			em[b[i]]=C++;
	}
	for(auto &x:A)
		x=em[x];
	for(auto &x:V)
		x=em[x];

	for(int i=0; i<n; i++){
		a[i]=A[i];
//		cout<<a[i]<<" ";

		add(a[i],1);
	}
	for(int i=0; i<n; i++){
		mp[a[i]].insert(n-i-1);
		up(a[i]);
	}
	//cout<<" ----> "<<rt->x<<endl;

	for(int i=0; i<q; i++){
		ll k=X[i];
		ll p=V[i];
		quer(k,p);
		PAS.pb(rt->x);
	}

	return PAS;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'void updt(int, int, node*&)':
bubblesort2.cpp:67:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt(l,l+r>>1,x->L);
         ~^~
bubblesort2.cpp:68:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt(l+r>>1,r,x->R);
       ~^~
bubblesort2.cpp: In function 'void updt1(int, int, node*&)':
bubblesort2.cpp:81:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt1(l,l+r>>1,x->L);
          ~^~
bubblesort2.cpp:82:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt1(l+r>>1,r,x->R);
        ~^~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:143:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<b.size(); i++){
               ~^~~~~~~~~

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