Submission #787542

#	Time	Username	Problem	Language	Result	Execution time	Memory
787542		vjudge1	Swap Swap Sort (CCO21_day1problem1)	C++14	25 / 25	2136 ms	58048 KiB

Main

#include <bits/stdc++.h>
#define ha(x,y) (100003ll*(x)+1ll*(y))
using namespace std;
constexpr int N=1e5+7,M=1e5+7,Q=1e6+7,X=3005;
int n,m,q,B;
int p[M],a[N];
vector<int> pos[M];
int id[M];
long long ans,f[X][X];
inline long long bf(){
    static struct Fwk{
        array<int,N> s;
        static inline int l(int x){return x&(-x);}
        inline void clear(){memset(s.begin()+1,0,m*sizeof(int));}
        inline void add(int x,int v){for(;x<=m;x+=l(x))s[x]+=v;}
        inline int sum(int x){int t{0};for(;x;x^=l(x))t+=s[x];return t;}
        inline int query(int l,int r){return sum(r)-sum(l-1);}
    }tr;
    long long s{0ll};
    for(int i{1};i<=n;++i){
        s+=tr.query(a[i]+1,m);
        tr.add(a[i],1);
    }
    for(int i{1};i<=n;++i){
        tr.add(a[i],-1);
    }
    return s;
}
inline void init(){
    int idc{0};
    static int cnt[X];
    for(int i{1};i<=m;++i){
        if((int)pos[i].size()>B){
            id[i]=++idc;
        }
    }
    for(int i{1};i<=n;++i){
        if(id[a[i]]){
            for(int j{1};j<=idc;++j){
                if(j==id[a[i]]) continue;
                f[j][id[a[i]]]+=cnt[j];
            }
            ++cnt[id[a[i]]];
        }
    }
}
inline long long query(int x,int y){
    if(pos[x].empty()||pos[y].empty()) return 0LL;
    if(id[x]&&id[y]) return f[id[x]][id[y]];
    int t{0};
    long long s{0ll};
    if(pos[x].size()<pos[y].size()){
        for(int i:pos[x]){
            t=upper_bound(pos[y].begin()+t,pos[y].end(),i)-pos[y].begin();
            s+=pos[y].size()-t;
        }
    }
    else{
        for(int i:pos[y]){
            t=upper_bound(pos[x].begin()+t,pos[x].end(),i)-pos[x].begin()-1;
            s+=t+1;
        }
    }
    return s;
}
signed main(){
    scanf("%d%d%d",&n,&m,&q);
    iota(p+1,p+m+1,1);
    B=max(int(cbrtl(2.0l*n*n/q/log2(n))),n/3000+1);
    for(int i{1};i<=n;++i){
        scanf("%d",&a[i]);
        pos[a[i]].emplace_back(i);
    }
    ans=bf();
    init();
    for(int i{1};i<=q;++i){
        int x;
        scanf("%d",&x);
        ans-=query(p[x+1],p[x]);
        ans+=query(p[x],p[x+1]);
        swap(p[x],p[x+1]);
        printf("%lld\n",ans);
    }
    return 0;
}
/*
    n^2/B^2+qBlogn
    min =n^2/B^2+qBlogn/2+qBlogn/2
        =3*cbrt(q^2*n^2log^2 n/4)
    n^2/B^2=qlogn*B/2
    B^3=2*n^2/(qlogn)
*/
/*
1 4 2 1 2
1 2 3 4
1 1 2 2 4
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d%d%d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf("%d",&x);
      |         ~~~~~^~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 5 / 5
• Subtask 4: 14 / 14