Submission #476072

#	Time	Username	Problem	Language	Result	Execution time	Memory
476072		aris12345678	Swap Swap Sort (CCO21_day1problem1)	C++14	6 / 25	5074 ms	2424 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int mxN = 100005;
int arr[mxN], bit[mxN], posi[mxN], po[mxN];

void upd(int pos, int n, int val) {
    while(pos <= n) {
        bit[pos] += val;
        pos += (pos&(-pos));
    }
}

long long ask(int pos) {
    long long ans = 0;
    while(pos > 0) {
        ans += 1LL*bit[pos];
        pos -= (pos&(-pos));
    }
    return ans;
}

int main() {
    int n, k, q;
    scanf("%d %d %d", &n, &k, &q);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
        posi[i] = i, po[i] = i;
    }
    while(q--) {
        int t;
        scanf("%d", &t);
        swap(posi[t], posi[t+1]);
        po[posi[t]]--, po[posi[t+1]]++;
        // cout << posi[t] << " " << po[posi[t]] << " " << posi[t+1] << " " << po[posi[t+1]] << "\n";
        fill(bit, bit+mxN, 0);
        long long ans = 0;
        for(int i = 1; i <= n; i++) {
            upd(po[arr[i]], n, 1);
            ans += (ask(n)-ask(po[arr[i]]));
            // cout << arr[i] << " " << po[arr[i]] << " " << ans << "\n";
            // cout << posi[i] << " " << po[posi[i]] << "\n";
        }
        // cout << "\n";
        printf("%lld\n", ans);
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d %d %d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
Main.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d", &t);
      |         ~~~~~^~~~~~~~~~

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