oj.uz

Submission #852550

# Submission time Handle Problem Language Result Execution time Memory
852550 2023-09-22T04:59:57 Z LucaDantas Swap Swap Sort (CCO21_day1problem1) C++17
6 / 25
 5000 ms 9552 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

constexpr int B = 1e5, maxn = 1e5+10;

vector<int> pos[maxn];

int a[maxn], id[maxn], cnt;

long long resp[maxn/B+10][maxn];

struct BIT {
    int bit[maxn];
    void upd(int x) {
        for(; x > 0; x-=x&-x)
            ++bit[x];
    }
    int query(int x) {
        int ans = 0;
        for(; x < maxn; x+=x&-x)
            ans += bit[x];
        return ans;
    }
} bit;

long long inversoes(int n) {
    long long ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += bit.query(a[i]+1);
        bit.upd(a[i]);
    }
    return ans;
}

int32_t main() {
    int n, k, q; scanf("%lld %lld %lld", &n, &k, &q);
    for(int i = 1; i <= n; i++)
        scanf("%lld", a+i), pos[a[i]].push_back(i);
    for(int cor = 1; cor <= k; cor++) {
        if(pos[cor].size() >= B) {
            assert(0);
            id[cor] = ++cnt;
            int qtd = 0;
            for(int i = n; i >= 1; i--) {
                if(a[i] == cor)
                    ++qtd;
                else
                    resp[cnt][a[i]] += qtd;
            }
        }
    }
    long long ans = inversoes(n);
    vector<int> perm(k);
    iota(perm.begin(), perm.end(), 1);
    while(q--) {
        auto get = [&](int x, int y) -> long long {
            if(pos[x].size() >= B)
                return resp[id[x]][y];
            if(pos[y].size() >= B)
                return 1ll * pos[x].size() * pos[y].size() - resp[id[y]][x];
            long long aq = 0;
            for(int i = 0, ptr = 0; i < (int)(pos[y].size()); i++) {
                for(; ptr < (int)(pos[x].size()) && pos[x][ptr] < pos[y][i]; ptr++);
                aq += pos[x].size() - ptr;
            }
            return aq;
        };
        int index; scanf("%lld", &index); --index;
        ans -= get(perm[index], perm[index+1]);
        swap(perm[index], perm[index+1]);
        ans += get(perm[index], perm[index+1]);
        printf("%lld\n", ans);
    }
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:38:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     int n, k, q; scanf("%lld %lld %lld", &n, &k, &q);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%lld", a+i), pos[a[i]].push_back(i);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:70:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         int index; scanf("%lld", &index); --index;
      |                    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 218 ms 5456 KB Output is correct
3 Correct 155 ms 5208 KB Output is correct
4 Correct 21 ms 5464 KB Output is correct
5 Correct 7 ms 5464 KB Output is correct
6 Correct 4 ms 5464 KB Output is correct
7 Correct 3 ms 5464 KB Output is correct
8 Correct 3 ms 5464 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 6268 KB Output is correct
2 Correct 71 ms 6356 KB Output is correct
3 Correct 11 ms 6488 KB Output is correct
4 Correct 11 ms 6488 KB Output is correct
5 Correct 14 ms 7260 KB Output is correct
6 Correct 16 ms 7256 KB Output is correct
7 Correct 18 ms 8272 KB Output is correct
8 Correct 23 ms 9552 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5020 ms 6564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 218 ms 5456 KB Output is correct
3 Correct 155 ms 5208 KB Output is correct
4 Correct 21 ms 5464 KB Output is correct
5 Correct 7 ms 5464 KB Output is correct
6 Correct 4 ms 5464 KB Output is correct
7 Correct 3 ms 5464 KB Output is correct
8 Correct 3 ms 5464 KB Output is correct
9 Correct 102 ms 6268 KB Output is correct
10 Correct 71 ms 6356 KB Output is correct
11 Correct 11 ms 6488 KB Output is correct
12 Correct 11 ms 6488 KB Output is correct
13 Correct 14 ms 7260 KB Output is correct
14 Correct 16 ms 7256 KB Output is correct
15 Correct 18 ms 8272 KB Output is correct
16 Correct 23 ms 9552 KB Output is correct
17 Execution timed out 5020 ms 6564 KB Time limit exceeded
18 Halted 0 ms 0 KB -