Submission #1271115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271115		trandangquang	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1573 ms	62396 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=5e5+5;
const int INF=1e9;

int n,q,a[N],x[N],v[N];
ii tmp[N+N]; int prv[N+N],nxt[N+N];

void compress(){
    rep(i,n) tmp[i]={a[i],i};
    rep(i,q) tmp[i+n]={v[i],i+n};

    sort(tmp, tmp+n+q);
    rep(i,n+q){
        if(tmp[i].se<n){
            a[tmp[i].se]=i;
        } else{
            v[tmp[i].se-n]=i;
        }
    }

    rep(i,n+q){
        int j=i;
        while(j<n+q && tmp[i].fi==tmp[j].fi) ++j;

        foru(k,i,j){
            prv[k]=i-1;
            nxt[k]=j;
        }

        i=j-1;
    }
}

vector<int> Answers;

int mx[N<<3],cnt[N<<3];
int lz[N<<3];

void apply(int id, int val){
    mx[id]+=val;
    lz[id]+=val;
}
void down(int id){
    if(lz[id]==0) return;
    apply(id<<1,lz[id]);
    apply(id<<1|1,lz[id]);
    lz[id]=0;
}

void updP(int x, int val){
    int id=1, l=0, r=n+q-1;
    while(l<r){
        down(id);
        int mid=(l+r)>>1;
        if(x<=mid){
            id=id<<1;
            r=mid;
        } else{
            id=id<<1|1;
            l=mid+1;
        }
    }

    if(val==-INF) cnt[id]=0;
    else cnt[id]=1;

    mx[id]=val;

    while(id>1){
        id/=2;
        mx[id]=max(mx[id<<1], mx[id<<1|1]);
        cnt[id]=cnt[id<<1] + cnt[id<<1|1];
    }
}

void updR(int u, int v, int val, int id=1, int l=0, int r=n+q-1){
    if(u>r||v<l) return;
    if(u<=l && r<=v){
        apply(id,val);
        return;
    }
    down(id);
    int mid=(l+r)>>1;
    updR(u,v,val,id<<1,l,mid);
    updR(u,v,val,id<<1|1,mid+1,r);
    mx[id]=max(mx[id<<1], mx[id<<1|1]);
    cnt[id]=cnt[id<<1] + cnt[id<<1|1];
}

int getCnt(int u, int v, int id=1, int l=0, int r=n+q-1){
    if(u>r||v<l) return 0;
    if(u<=l&&r<=v) return cnt[id];
    int mid=(l+r)>>1;
    return getCnt(u,v,id<<1,l,mid) + getCnt(u,v,id<<1|1,mid+1,r);
}

void del(int x){
    updP(x,-INF);
    updR(prv[x]+1, n+q-1, 1);
}

void add(int x, int i){
    int cntS=getCnt(0,nxt[x]-1);
    updR(prv[x]+1, n+q-1, -1);
    updP(x, i-cntS);
}

void mainSolve(){
    rep(i,n) add(a[i],i);
    rep(i,q){
        del(a[x[i]]);
        a[x[i]]=v[i];
        add(a[x[i]],x[i]);

        Answers.eb(mx[1]);
    }
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
    n=sz(A); q=sz(X);
    rep(i,sz(A)) a[i]=A[i];
    rep(i,sz(X)) x[i]=X[i], v[i]=V[i];

    compress();
    mainSolve();

    return Answers;
}

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