Submission #926561

#	Time	Username	Problem	Language	Result	Execution time	Memory
926561		winter0101	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2284 ms	171448 KiB

bubblesort2

#include<bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=1e6+9;
int st[maxn<<2],lazy[maxn<<2];
int cnt[maxn];
void push(int id){
if (lazy[id]){
st[id<<1]+=lazy[id];
st[id<<1|1]+=lazy[id];
lazy[id<<1]+=lazy[id];
lazy[id<<1|1]+=lazy[id];
lazy[id]=0;
}
}
void update(int id,int l,int r,int u,int v,int val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
    st[id]+=val;
    lazy[id]+=val;
    return;
}
int mid=(l+r)>>1;
push(id);
update(id<<1,l,mid,u,v,val);
update(id<<1|1,mid+1,r,u,v,val);
st[id]=max(st[id<<1],st[id<<1|1]);
}
set<int>id[maxn];
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
vector<int>value;
for(auto v:A)value.pb(v);
for(auto v:V)value.pb(v);
sort(all(value));
value.resize(distance(value.begin(),unique(all(value))));
for(auto &v:A)v=lower_bound(all(value),v)-value.begin()+1;
for(auto &v:V)v=lower_bound(all(value),v)-value.begin()+1;
int n=sz(value);
for1(i,1,n)id[i].insert(0);
for (auto v:A)cnt[v]++;
for1(i,0,sz(A)-1)id[A[i]].insert(i+1);
for1(i,1,n){
cnt[i]+=cnt[i-1];
auto it=id[i].end();
it--;
update(1,1,n,i,i,(*it)-cnt[i]);
}
int q=sz(X);
vector<int>answer(q);
for1(i,0,q-1){
int oldv=A[X[i]],newv=V[i];
update(1,1,n,oldv,n,1);
auto mx=[](int vl){
auto it=id[vl].end();
it--;
return (*it);
};
update(1,1,n,oldv,oldv,-mx(oldv));
update(1,1,n,newv,newv,-mx(newv));
id[oldv].erase(X[i]+1);
update(1,1,n,newv,n,-1);
id[newv].insert(X[i]+1);
A[X[i]]=V[i];
update(1,1,n,oldv,oldv,mx(oldv));
update(1,1,n,newv,newv,mx(newv));
answer[i]=st[1];
}
return answer;
}

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