Submission #696418

#	Time	Username	Problem	Language	Result	Execution time	Memory
696418		benedict0724	Swap Swap Sort (CCO21_day1problem1)	C++17	25 / 25	1049 ms	55680 KiB

Main

#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>

using namespace std;
typedef long long ll;

int T[100002], n, k, q;
int A[100002], per[100002];
int num[100002];
vector<int> idx[100002];
ll cnt[100002];
vector<vector<ll>> pre;

void upd(int x, int v)
{
    for(int i=x;i<=n;i+=(i&-i)) T[i] += v;
}

int f(int x)
{
    int ret = 0;
    for(int i=x;i;i^=(i&-i)) ret += T[i];
    return ret;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> k >> q;
    for(int i=1;i<=k;i++) per[i] = i;
    
    int B = 100;
    
    ll ans = 0;
    for(int i=0;i<n;i++)
    {
        cin >> A[i];
        
        upd(A[i], 1);
        ans += i + 1 - f(A[i]);
        
        idx[A[i]].push_back(i);
        cnt[A[i]]++;
    }
    
    int asdf = 0;
    for(int i=1;i<=k;i++)
    {
        if(cnt[i] > B)
        {
            vector<ll> v(k+1);
            ll now = 0;
            for(int j=0;j<n;j++)
            {
                if(A[j] == i) now++;
                else v[A[j]] += now;
            }
            pre.push_back(v);
            num[i] = asdf++;
        }
    }
    
    for(int i=1;i<=q;i++)
    {
        int x; cin >> x;
        int a = per[x], b = per[x+1];
        
        swap(per[x], per[x+1]);
        
        if(cnt[a] > B)
        {
            ans -= cnt[a] * cnt[b];
            ans += 2 * pre[num[a]][b];
            
            cout << ans << "\n";
            continue;
        }
        if(cnt[b] > B)
        {
            ans -= 2 * pre[num[b]][a];
            ans += cnt[a] * cnt[b];
            
            cout << ans << "\n";
            continue;
        }
        
        ll tmp = 0;
        for(int t1=0,t2=0;t2<cnt[b];)
        {
            if(t1 == cnt[a])
            {
                t2++;
                tmp += t1;
            }
            else if(idx[a][t1] < idx[b][t2]) t1++;
            else
            {
                t2++;
                tmp += t1;
            }
        }
        ans += 2 * tmp;
        ans -= cnt[a] * cnt[b];
        cout << ans << "\n";
    }
}

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