oj.uz

Submission #852546

# Submission time Handle Problem Language Result Execution time Memory
852546 2023-09-22T04:54:43 Z LucaDantas Swap Swap Sort (CCO21_day1problem1) C++17
0 / 25
 5000 ms 6648 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 = (int)(pos[y].size())-1, ptr = (int)(pos[x].size())-1; i >= 0; i--) {
                int now = 0;
                for(; ptr >= 0 && pos[x][ptr] > pos[y][i]; ptr--)
                    ++now;
                aq += now;
            }
            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:72:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         int index; scanf("%lld", &index); --index;
      |                    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Incorrect 218 ms 5460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 6248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5044 ms 6648 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 Incorrect 218 ms 5460 KB Output isn't correct
3 Halted 0 ms 0 KB -