Submission #851996

#	Time	Username	Problem	Language	Result	Execution time	Memory
851996		MrM7md	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	28 ms	63320 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
// #define int long long
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(),a.end()
const int N=2e5 + 3;
const int MOD=1e9+7;
const int off=(1<<20);
 
int t[off*2],dis[off*2],lazy[off*2];
void upd2(int x,int v){
	x+=off;
	t[x]+=v;
	while(x/=2){
		t[x]=t[x*2]+t[x*2+1];
	}
}
int get2(int x,int l,int r,int st,int en){
	if(r<st||l>en)return 0;
	if(r<=en&&l>=st){
		return t[x];
	}
	int md=(l+r)/2;
	return get2(x*2,l,md,st,en)+get2(x*2+1,md+1,r,st,en);
}
void push(int x,int l,int r){
   if(lazy[x]==0)return;
   if(l!=r){
      lazy[x*2]+=lazy[x];
      lazy[x*2+1]+=lazy[x];
   }
   dis[x]+=lazy[x];
   lazy[x]=0;
}
void upd(int x,int l,int r,int st,int en,int df){
   push(x,l,r);
   if(r<st||l>en)return ;
   if(l>=st&&r<=en){
      lazy[x]+=df;
      push(x,l,r);
      return ;
   }
   int md=(l+r)/2;
   upd(x*2,l,md,st,en,df);
   upd(x*2+1,md+1,r,st,en,df);
   dis[x]=max(dis[x*2],dis[x*2+1]);

}
int get(int x,int l,int r,int st,int en){
   push(x,l,r);
   if(r<st||l>en)return INT_MIN;
   if(l>=st&&r<=en){
      return dis[x];
   }
   int md=(l+r)/2;
   int ll=get(x*2,l,md,st,en);
   int rr=get(x*2+1,md+1,r,st,en);
   return max(ll,rr);
}

 
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	for(int i=0;i<off*2;i++)dis[i]=INT_MIN;
	int q=X.size(),n=A.size();
	vector<int>ans;
	set<int>st;
	for(auto it:A)st.insert(it);
	for(auto it:V)st.insert(it);
	int cnt=1;
	map<int,int>mp;
	for(auto it:st)mp[it]=cnt++;
	vector<set<int>>vv(1e6+20);
	for(int i=0;i<n;i++){
		int a=A[i];
		upd2(mp[a],1);
		vv[mp[a]].insert(i+1);
	}
	int cur=0;
	for(int i=1;i<=cnt;i++){
		if(vv[i].empty()){
			// upd(1,1,off-1,i+1,i+1,INT_MIN);
			continue;
		}
		cur+=vv[i].size();
		upd(1,1,off-1,i+1,i+1,(-1*dis[i+off])+(*vv[i].rbegin())-cur);
	}
	for(int j=0;j<q;j++){
		int x=X[j],v=mp[V[j]];
		int a=mp[A[x]],prev;
		upd(1,1,off-1,a+1,cnt+1,-1);
		upd(1,1,off-1,v+1,cnt+1,1);
		upd(1,1,off-1,a+1,a+1,-1*dis[a+off]);

		upd2(a,-1);
		vv[a].erase(x+1);
		vv[v].insert(x+1);
		upd2(v,1);

		prev=get2(1,1,off-1,1,v+1);
		// cout<<prev<<' ';
		upd(1,1,off-1,v+1,v+1,-1*dis[v+off]);
		upd(1,1,off-1,v+1,v+1,(*vv[v].rbegin())-prev);
		cout<<dis[1]<<endl;
		if(vv[a].size()&&a!=v){
			prev=get2(1,1,off-1,1,a);
			upd(1,1,off-1,a+1,a+1,(*vv[a].rbegin())-prev);
		}
		A[x]=V[j];
		// ans.pb(dis[1]);
		ans.pb(dis[1]);
	}
	return ans;

}

/*


1 2 5 7 3 5 4







*/

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