Submission #697814

#	Time	Username	Problem	Language	Result	Execution time	Memory
697814		azberjibiou	Swap Swap Sort (CCO21_day1problem1)	C++17	6 / 25	5039 ms	85876 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;
            mp[pii(n2, n1)]=cnt[n1]*cnt[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)
{
    return sinv(a, b);
    if(cnt[a]<cnt[b])   return cnt[a]*cnt[b]-inv(b, a);
    if(cnt[b]>=M)  return mp[pii(a, b)];
    if(cnt[a]>=M && cnt[b]<M)   return 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);
    assert(big.size()<=M+4);
    make_bb();
    assert(mp.size()<=M*M);
    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:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i=0;i<v[b].size();i++)
      |                 ~^~~~~~~~~~~~
Main.cpp:75: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]
   75 |         while(idx!=v[a].size() && v[a][idx]<v[b][i])    idx++;
      |               ~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp: In function 'int main()':
Main.cpp:96:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   96 |     assert(big.size()<=M+4);
      |            ~~~~~~~~~~^~~~~

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