Submission #696363

#	Time	Username	Problem	Language	Result	Execution time	Memory
696363		Cross_Ratio	Swap Swap Sort (CCO21_day1problem1)	C++14	25 / 25	3774 ms	55180 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int A[100005];
int B[100005];
int C[100005];
vector<int> D[100005];
struct SegTree {
    vector<int> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void Edit(int n, int a) {
        n += MAX/2;
        seg[n] += a;
        n /= 2;
        while(n) {
            seg[n] = seg[2*n] + seg[2*n+1];
            n /= 2;
        }
    }
    int sum(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return sum(s, e, 2*n, ns, mid) + sum(s, e, 2*n+1, mid, ne);
    }
};
int id[100005];
int sB = 200;
int E[500][100005];
int calc(int x, int y) {
    if(id[x]!=-1) return E[id[x]][y];
    if(id[y]!=-1) return B[x] * B[y] - E[id[y]][x];
    int sum = 0;
    for(int n : D[y]) {
        sum += lower_bound(D[x].begin(),D[x].end(),n) - D[x].begin();
    }
    return sum;
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, K, Q;
    cin >> N >> K >> Q;
    int i, j;
    for(i=0;i<N;i++) {
        cin >> A[i];
        B[A[i]]++;
        D[A[i]].push_back(i);
    }
    for(i=1;i<=K;i++) C[i] = i;
    int ans = 0;
    SegTree tree(K+1);
    int MAX = tree.MAX;
    for(i=0;i<N;i++) {
        ans += tree.sum(A[i]+1, K+1, 1, 0, MAX/2);
        tree.Edit(A[i], 1);
    }
    int id_cnt = 0;
    for(i=1;i<=K;i++) id[i] = -1;
    for(i=1;i<=K;i++) {
        if(B[i] >= sB) {
            id[i] = id_cnt;
            int v = 0;
            for(j=0;j<N;j++) {
                if(A[j]==i) v++;
                E[id_cnt][A[j]] += v;
            }
            id_cnt++;
        }
    }
    while(Q--) {
        int k;
        cin >> k;
        int v1 = C[k], v2 = C[k+1];
        int val = calc(v2, v1);
        ans += B[v1] * B[v2] - 2*val;
        C[k] = v2, C[k+1] = v1;
        cout << ans << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In member function 'long long int SegTree::sum(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:29:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~

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