oj.uz

Submission #411617

# Submission time Handle Problem Language Result Execution time Memory
411617 2021-05-25T15:43:32 Z emuyumi Swap Swap Sort (CCO21_day1problem1) C++17
25 / 25
 1777 ms 251992 KB 
#include <bits/stdc++.h>

using namespace std;
#define ms(x,a) memset(x,a,sizeof x)
typedef long long ll;
const int mod=1e9+7, inf=0x3f3f3f3f, MAXN=1e5+1, MAXQ=2e6+1, SZ=5000;

int n, k, q;
int arr[MAXN], tar[MAXN];
int a[MAXQ], b[MAXQ];
ll ans[MAXQ], bad[MAXQ];
int id[MAXN];
set<int> ss;
int cnt[SZ+10];
ll mp[SZ+10][SZ+10];

struct Fenwick{
    int a[MAXN];
    void ins(int i, int v=1){ for (;i<MAXN;i+=i&-i) a[i]+=v; }
    int qry(int i){
        ll ret=0;
        for (;i;i-=i&-i) ret+=a[i];
        return ret;
    }
} bit;

void build(){
    for (int bl=0;bl*SZ<=n;++bl){
        int l=bl*SZ, r=min(n,(bl+1)*SZ-1);
        for (int i=l;i<=r;++i) ss.insert(arr[i]);
        int poi=0;
        for (int x:ss) id[x]=++poi;
        for (int i=l;i<=r;++i){
            arr[i]=id[arr[i]];
            for (int j=1;j<=poi;++j){
                mp[arr[i]][j]+=cnt[j];
            }
            cnt[arr[i]]++;
        }
        // compute answers
        for (int i=1;i<=2*q;++i){
            int aa=id[a[i]];
            int bb=id[b[i]];
            if (aa&&bb) ans[i]+=mp[aa][bb];
            if (aa) ans[i]+=bad[i]*cnt[aa];
            if (bb) bad[i]+=cnt[bb];
        }
        for (int i=1;i<=poi;++i) ms(mp[i],0);
        // resetting
        ss.clear(), ms(id,0);
        ms(cnt,0);
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k >> q;
    for (int i=1;i<=n;++i) cin >> arr[i];
    iota(tar+1,tar+1+n,1);
    for (int i=1;i<=q;++i){
        int j; cin >> j;
        a[i*2-1]=tar[j];
        b[i*2-1]=tar[j+1];
        a[i*2]=b[i*2-1];
        b[i*2]=a[i*2-1];
        swap(tar[j],tar[j+1]);
    }
    ll tot=0;
    for (int i=1;i<=n;++i){
        bit.ins(arr[i]);
        tot+=i-bit.qry(arr[i]);
    }
    build();
    for (int i=1;i<=q;++i){
        tot-=ans[i*2-1];
        tot+=ans[i*2];
        // cout << cntinv(a[i],b[i]) << " " << cntinv(b[i],a[i]) << '\n';
        cout << tot << '\n';
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 3 ms 1228 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Correct 4 ms 2124 KB Output is correct
5 Correct 5 ms 5068 KB Output is correct
6 Correct 17 ms 20748 KB Output is correct
7 Correct 28 ms 40008 KB Output is correct
8 Correct 84 ms 126768 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1620 KB Output is correct
2 Correct 17 ms 1740 KB Output is correct
3 Correct 30 ms 5564 KB Output is correct
4 Correct 229 ms 40640 KB Output is correct
5 Correct 791 ms 126916 KB Output is correct
6 Correct 1006 ms 157280 KB Output is correct
7 Correct 1192 ms 189396 KB Output is correct
8 Correct 1276 ms 194252 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 59676 KB Output is correct
2 Correct 378 ms 59716 KB Output is correct
3 Correct 401 ms 60568 KB Output is correct
4 Correct 436 ms 63556 KB Output is correct
5 Correct 562 ms 75244 KB Output is correct
6 Correct 611 ms 79180 KB Output is correct
7 Correct 630 ms 79196 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 3 ms 1228 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Correct 4 ms 2124 KB Output is correct
5 Correct 5 ms 5068 KB Output is correct
6 Correct 17 ms 20748 KB Output is correct
7 Correct 28 ms 40008 KB Output is correct
8 Correct 84 ms 126768 KB Output is correct
9 Correct 14 ms 1620 KB Output is correct
10 Correct 17 ms 1740 KB Output is correct
11 Correct 30 ms 5564 KB Output is correct
12 Correct 229 ms 40640 KB Output is correct
13 Correct 791 ms 126916 KB Output is correct
14 Correct 1006 ms 157280 KB Output is correct
15 Correct 1192 ms 189396 KB Output is correct
16 Correct 1276 ms 194252 KB Output is correct
17 Correct 380 ms 59676 KB Output is correct
18 Correct 378 ms 59716 KB Output is correct
19 Correct 401 ms 60568 KB Output is correct
20 Correct 436 ms 63556 KB Output is correct
21 Correct 562 ms 75244 KB Output is correct
22 Correct 611 ms 79180 KB Output is correct
23 Correct 630 ms 79196 KB Output is correct
24 Correct 786 ms 98604 KB Output is correct
25 Correct 1182 ms 132600 KB Output is correct
26 Correct 1560 ms 185480 KB Output is correct
27 Correct 1569 ms 215992 KB Output is correct
28 Correct 1572 ms 234168 KB Output is correct
29 Correct 1582 ms 247632 KB Output is correct
30 Correct 1624 ms 251968 KB Output is correct
31 Correct 1661 ms 251992 KB Output is correct
32 Correct 988 ms 166520 KB Output is correct
33 Correct 595 ms 75360 KB Output is correct
34 Correct 615 ms 79172 KB Output is correct
35 Correct 678 ms 83036 KB Output is correct
36 Correct 1028 ms 98656 KB Output is correct
37 Correct 1677 ms 130496 KB Output is correct
38 Correct 1777 ms 153468 KB Output is correct
39 Correct 1676 ms 251844 KB Output is correct
40 Correct 1477 ms 225848 KB Output is correct
41 Correct 1423 ms 213488 KB Output is correct
42 Correct 1124 ms 163116 KB Output is correct
43 Correct 1146 ms 166032 KB Output is correct
44 Correct 1092 ms 160292 KB Output is correct
45 Correct 1094 ms 161680 KB Output is correct
46 Correct 1555 ms 219240 KB Output is correct
47 Correct 1492 ms 193608 KB Output is correct
48 Correct 1429 ms 118684 KB Output is correct
49 Correct 1653 ms 131452 KB Output is correct
50 Correct 1039 ms 158412 KB Output is correct
51 Correct 553 ms 77960 KB Output is correct
52 Correct 484 ms 64648 KB Output is correct
53 Correct 1055 ms 161616 KB Output is correct
54 Correct 1110 ms 162612 KB Output is correct
55 Correct 1 ms 844 KB Output is correct