| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1159037 | Mingyuanz | Bubble Sort 2 (JOI18_bubblesort2) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define INF (int)9e18
#define MOD (int)(1e9+7)
#define MAXN 500069
#define enl '\n'
#define DB(CODE) cout<<'\t'<<CODE<<'\n';
#define SP <<' '<<
//#define int long long
typedef long long ll;
using namespace std;
struct node{
int mx;
int add;
};
int n,q,N;
node seg[6*MAXN];
node createnode(int val){
node nd;
nd.mx=val;
nd.add=0;
return nd;
}
node mergenode(node left,node right){
node nd;
nd.mx=max(left.mx,right.mx);
nd.add=0;
return nd;
}
void upd_push(int idx){
if(seg[idx].add){
seg[idx].mx+=seg[idx].add;
seg[2*idx].add+=seg[idx].add;
seg[2*idx+1].add+=seg[idx].add;
seg[idx].add=0;
}
}
void build(int *arr,int idx=1,int l=0,int r=N-1){
if(l==r){
seg[idx]=createnode(arr[l]);
return;
}
int m=(l+r)/2;
build(arr,idx*2,l,m);
build(arr,idx*2+1,m+1,r);
seg[idx]=mergenode(seg[idx*2],seg[idx*2+1]);
}
node findmin(int a,int b,int idx=1,int l=0,int r=N-1){
if(r<a || b<l) return createnode(INF);
upd_push(idx);
if(a<=l && r<=b) return seg[idx];
int m=(l+r)/2;
return mergenode(findmin(a,b,idx*2,l,m),findmin(a,b,idx*2+1,m+1,r));
}
void update(int i,int val,int idx=1,int l=0,int r=N-1){
if(l==r){
seg[idx]=createnode(val);
return;
}
upd_push(idx);
int m=(l+r)/2;
if(i<=m) update(i,val,idx*2,l,m),upd_push(2*idx+1);
else update(i,val,idx*2+1,m+1,r),upd_push(2*idx);
seg[idx]=mergenode(seg[idx*2],seg[idx*2+1]);
}
void range_add(int a,int b,int val,int idx=1,int l=0,int r=N-1){
if(r<a || b<l) return;
upd_push(idx);
if(a<=l && r<=b){
seg[idx].add+=val;
return;
}
int m=(l+r)/2;
range_add(a,b,val,idx*2,l,m);
range_add(a,b,val,idx*2+1,m+1,r);
upd_push(idx*2),upd_push(idx*2+1);
seg[idx]=mergenode(seg[idx*2],seg[idx*2+1]);
}
int fw[MAXN];
void createtree(){
for(int i=1; i<=N; i++){
int j=(i&-i)+i;
if(j<=N) fw[j]+=fw[i];
}
}
int prefixsum(int i){
int sum=0;
while(i){
sum+=fw[i];
i&=~(i&-i);
}
return sum;
}
void add(int i,int d){
while(i<=N){
fw[i]+=d;
i+=i&-i;
}
}
void fw_range_add(int l,int r,int d){
add(l,d);
add(r+1,-d);
}
vector<int> countScans(vector<int> &arr,vector<int> &x,vector<int> &w){
vector<int> ans;
set<int> valset;
for(auto &v: arr) valset.insert(v);
for(auto &v: w) valset.insert(v);
vector<int> val;
for(auto &v: valset) val.pb(v);
for(auto &v: arr) v=lower_bound(val.begin(),val.end(),v)-val.begin();
for(auto &v: w) v=lower_bound(val.begin(),val.end(),v)-val.begin();
N=val.size();
set<int> pos[N];
for(int i=0; i<n; i++){
pos[arr[i]].insert(i);
fw[i+1]++;
}
createtree();
int cur[N];
for(int i=0; i<N; i++){
if(pos[i].empty()) cur[i]=-INF;
else{
auto it=pos[i].end();
it--;
cur[i]=*it-prefixsum(i);
}
}
build(cur);
for(int i=0; i<q; i++){
pos[arr[x[i]]].erase(x[i]);
fw_range_add(arr[x[i]]+1,N,-1);
if(pos[arr[x[i]]].empty()) cur[arr[x[i]]]=-INF;
else{
auto it=pos[arr[x[i]]].end();
it--;
cur[arr[x[i]]]=*it-prefixsum(arr[x[i]]);
}
update(arr[x[i]],cur[arr[x[i]]]);
range_add(arr[x[i]]+1,N-1,1);
arr[x[i]]=w[i];
pos[arr[x[i]]].insert(x[i]);
fw_range_add(arr[x[i]]+1,N,1);
if(pos[arr[x[i]]].empty()) cur[arr[x[i]]]=-INF;
else{
auto it=pos[arr[x[i]]].end();
it--;
cur[arr[x[i]]]=*it-prefixsum(arr[x[i]]);
}
update(arr[x[i]],cur[arr[x[i]]]);
range_add(arr[x[i]]+1,N-1,-1);
ans.pb(seg[1].mx);
}
return ans;
}