Submission #854303

#	Time	Username	Problem	Language	Result	Execution time	Memory
854303		Lobo	Swap Swap Sort (CCO21_day1problem1)	C++17	25 / 25	653 ms	302544 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3","unroll-loops")
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define lol long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e5+10;
const int B = 70;

int n, k, q, a[maxn], id[maxn], cntid, tr[4*maxn];
vector<int> fq[maxn];
vector<vector<int>> inv;

void upd(int no, int l, int r, int pos, int val) {
    if(l > pos || r < pos) return;
    if(l == r) {
        tr[no]+= val;
        return;
    }
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    upd(lc,l,mid,pos,val);
    upd(rc,mid+1,r,pos,val);
    tr[no] = tr[lc]+tr[rc];
}

int qry(int no, int l, int r, int ll, int rr) {
    if(l > rr || r < ll) return 0;
    if(l >= ll && r <= rr) return tr[no];
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    return qry(lc,l,mid,ll,rr)+qry(rc,mid+1,r,ll,rr);
}

void solve() {
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        fq[a[i]].pb(i);
    }


    for(int x = 1; x <= k; x++) {
        if(fq[x].size() >= B) {
            id[x] = cntid++;
            inv.pb(vector<int>(k+1,0));

            int cntafter = fq[x].size();
            for(int i = 1; i <= n; i++) {
                if(a[i] == x) cntafter--;
                else {
                    inv[id[x]][a[i]]+= cntafter;
                }
            }
        }
    }

    lol invcur = 0;
    for(int i = 1; i <= n; i++) {
        invcur+= qry(1,1,k,a[i]+1,k);
        upd(1,1,k,a[i],1);
    }

    vector<int> p(k+1); for(int i = 1; i <= k; i++) p[i] = i;

    for(int i = 1; i <= q; i++) {
        int j; cin >> j;
        int l = p[j];
        int r = p[j+1];

        lol lr,rl;

        if(fq[l].size() >= B) {
            lr = inv[id[l]][r];
            rl = fq[l].size()*fq[r].size() - lr;
        }
        else if(fq[r].size() >= B) {
            rl = inv[id[r]][l];
            lr = fq[l].size()*fq[r].size() - rl;
        }
        else {
            int cntr = 0;
            lr = 0;
            int pl = 0;
            int pr = 0;
            while(pl != fq[l].size() || pr != fq[r].size()) {
                if(pr == fq[r].size() || (pl != fq[l].size() && fq[l][pl] < fq[r][pr])) {
                    lr+= cntr;
                    pl++;
                }
                else {
                    cntr++;
                    pr++;
                }
            }
            rl = fq[l].size()*fq[r].size() - lr;
        }

        invcur+= -lr+rl;
        swap(p[j],p[j+1]);
        cout << invcur << endl;
    }

}
    
int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             while(pl != fq[l].size() || pr != fq[r].size()) {
      |                   ~~~^~~~~~~~~~~~~~~
Main.cpp:92:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             while(pl != fq[l].size() || pr != fq[r].size()) {
      |                                         ~~~^~~~~~~~~~~~~~~
Main.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                 if(pr == fq[r].size() || (pl != fq[l].size() && fq[l][pl] < fq[r][pr])) {
      |                    ~~~^~~~~~~~~~~~~~~
Main.cpp:93:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                 if(pr == fq[r].size() || (pl != fq[l].size() && fq[l][pl] < fq[r][pr])) {
      |                                           ~~~^~~~~~~~~~~~~~~

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