| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 851943 | MrM7md | Bubble Sort 2 (JOI18_bubblesort2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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>=500000){
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);
}
return ans;
}
// 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;
}