Submission #697830

#	Time	Username	Problem	Language	Result	Execution time	Memory
697830		azberjibiou	Swap Swap Sort (CCO21_day1problem1)	C++17	8 / 25	2632 ms	96580 KiB

Main

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pii pair<int, int>
typedef long long ll;
using namespace std;
const int mxN=100005;
ll N, M, K, Q;
int A[mxN];
ll cnt[mxN];
int B[mxN];
vector <int> v[mxN];
vector <int> big;
vector <ll> pref[mxN];
map <pii, ll> mp;  ///mp[a, b] = a ... b 의 개수
ll ans;
void make_bb()
{
    for(int i=0;i<big.size();i++)
    {
        for(int j=i+1;j<big.size();j++)
        {
            int n1=big[i], n2=big[j];
            ll inv=0;
            int idx=0;
            for(int k=0;k<v[n2].size();k++)
            {
                while(idx!=v[n1].size() && v[n1][idx]<v[n2][k]) idx++;
                inv+=idx;
            }
            mp[pii(n1, n2)]=inv;
        }
    }
}
void make_pref()
{
    for(int now : big)
    {
        pref[now].resize(N+1);
        pref[now][0]=0;
        for(int i=1;i<=N;i++)   pref[now][i]=pref[now][i-1]+(A[i]==now);
    }
}
ll fen[mxN];
void upd(int now, int x){while(now<=N)  fen[now]+=x, now+=(now&(-now));}
ll sum(int now)
{
    int ret=0;
    while(now)  ret+=fen[now], now-=(now&(-now));
    return ret;
}
ll solv(int s, int e){return sum(e)-sum(s-1);}
void init_inv()
{
    for(int i=K;i>=1;i--)
    {
        for(int x : v[i])   ans+=sum(x);
        for(int x : v[i])   upd(x, 1);
    }
}
ll minv(int a, int b)
{
    ll ret=0;
    assert(cnt[b]<M);
    for(int x : v[b])   ret+=pref[a][x];
    return ret;
}
ll sinv(int a, int b)
{
    ll ret=0, idx=0;
    for(int i=0;i<v[b].size();i++)
    {
        while(idx!=v[a].size() && v[a][idx]<v[b][i])    idx++;
        ret+=idx;
    }
    return ret;
}
ll inv(int a, int b)
{
    if(cnt[a]<cnt[b])   return cnt[a]*cnt[b]-inv(b, a);
    if(cnt[b]>=M)
    {
        if(a<b) return mp[pii(a, b)];
        else    return cnt[a]*cnt[b]-mp[pii(b, a)];
    }
    if(cnt[a]>=M && cnt[b]<M)   minv(a, b);
    else    return sinv(a, b);
}
int main()
{
    gibon
    cin >> N >> K >> Q;
    for(int i=1;i<=N;i++)   cin >> A[i], v[A[i]].push_back(i), cnt[A[i]]++;
    M=1;
    while((M+1)*(M+1)<=N)   M++;
    for(int i=1;i<=K;i++)   if(cnt[i]>=M)   big.push_back(i);
    make_bb();
    make_pref();
    init_inv();
    for(int i=1;i<=K;i++)   B[i]=i;
    while(Q--)
    {
        int a;
        cin >> a;
        ll ninv=inv(B[a+1], B[a]);
        ans-=ninv;
        ans+=cnt[B[a]]*cnt[B[a+1]]-ninv;
        swap(B[a], B[a+1]);
        cout << ans << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'void make_bb()':
Main.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<big.size();i++)
      |                 ~^~~~~~~~~~~
Main.cpp:22:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int j=i+1;j<big.size();j++)
      |                       ~^~~~~~~~~~~
Main.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             for(int k=0;k<v[n2].size();k++)
      |                         ~^~~~~~~~~~~~~
Main.cpp:29:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |                 while(idx!=v[n1].size() && v[n1][idx]<v[n2][k]) idx++;
      |                       ~~~^~~~~~~~~~~~~~
Main.cpp: In function 'll sinv(int, int)':
Main.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=0;i<v[b].size();i++)
      |                 ~^~~~~~~~~~~~
Main.cpp:74:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         while(idx!=v[a].size() && v[a][idx]<v[b][i])    idx++;
      |               ~~~^~~~~~~~~~~~~
Main.cpp: In function 'll inv(int, int)':
Main.cpp:87:37: warning: control reaches end of non-void function [-Wreturn-type]
   87 |     if(cnt[a]>=M && cnt[b]<M)   minv(a, b);
      |                                 ~~~~^~~~~~

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