Submission #851946

#	Time	Username	Problem	Language	Result	Execution time	Memory
851946		MrM7md	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9031 ms	1748 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 mx[off*2],mn[off*2];
// void upd(int x,int v){
// 	x+=off;
// 	mx[x]=v;
// 	mn[x]=v;
// 	while(x/=2){
// 		mx[x]=max(mx[x*2],mx[x*2+1]);
// 		if(mn[x*2]==0)mn[x*2]=INT_MAX;
// 		if(mn[x*2+1]==0)mn[x*2+1]=INT_MAX;
// 		mn[x]=min(mn[x*2],mn[x*2+1]);
// 	}
// }
// int get(int x,int l,int r,int st,int en,int val){
// 	if(r<st||l>en)return 0;
//    if(l>=st&&r<=en){
//       // if(mn[x]>val)
//       return r-l+1;
//       // if(mx[x]<=val)
//       return 0;
//    }
//    int mid=(l+r)/2;
//    return (get(x*2,l,mid,st,en,val)+get(x*2+1,mid+1,r,st,en,val));
// }
 
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){

	vector<int>ans;
	int q=X.size(),n=A.size();
	if(n>=50000||q>=50000){
		return ans;
		vector<set<int>>vv(101);
		for(int i=0;i<n;i++){
			vv[A[i]].insert(i+1);
		}
		for(int j=0;j<q;j++){
			int x=X[j],v=V[j];
			vv[A[x]].erase(x+1);
			vv[v].insert(x+1);
			A[x]=v;
			int cur=0,mxx=0;
			for(int i=1;i<=100;i++){
				if(vv[i].empty())continue;
				cur+=vv[i].size();
				mxx=max(mxx,(*vv[i].rbegin())-cur);
			}
			ans.pb(mxx);
		}
	}
	// int dis[n]={0};
	multiset<int>ms;
	vector<pair<int,int>>per,yo;
	for(int i=0;i<n;i++)per.pb({A[i],i});
   for(int j=0;j<q;j++){
      int x=X[j],v=V[j];
		A[x]=v;
		per[x]={v,x};
		yo=per;
		sort(all(yo));
		int mxx=0;
 		for(int i=0;i<n;i++){
			mxx=max(mxx,yo[i].S-i);
		}
		
      ans.pb(mxx);
   }
	return ans;
}

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