oj.uz

Submission #576294

# Submission time Handle Problem Language Result Execution time Memory
576294 2022-06-13T00:41:29 Z eecs Swap Swap Sort (CCO21_day1problem1) C++17
11 / 25
 5000 ms 148212 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;
int n, m, q, a[maxn], p[maxn];
vector<int> V[maxn];

namespace BIT {
int c[maxn];

void add(int p, int v) {
    for (; p <= m; p += p & -p) c[p] += v;
}

int query(int p) {
    int s = 0;
    for (; p; p -= p & -p) s += c[p];
    return s;
}
} // namespace BIT

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i], V[a[i]].push_back(i);
    }
    iota(p + 1, p + m + 1, 1);
    long long ans = 0;
    for (int i = n; i; i--) {
        ans += BIT::query(a[i] - 1), BIT::add(a[i], 1);
    }
    auto solve = [&](int x, int y) {
        static map<pair<int, int>, long long> mp;
        if (mp.count({x, y})) return mp[{x, y}];
        long long s = 0;
        if (V[x].size() < V[y].size()) {
            for (int i : V[x]) {
                s += V[y].end() - lower_bound(V[y].begin(), V[y].end(), i);
            }
        } else {
            for (int i : V[y]) {
                s += lower_bound(V[x].begin(), V[x].end(), i) - V[x].begin();
            }
        }
        return mp[{x, y}] = s;
    };
    while (q--) {
        int k;
        cin >> k;
        ans += solve(p[k], p[k + 1]);
        swap(p[k], p[k + 1]), ans -= solve(p[k], p[k + 1]);
        cout << ans << "\n";
    }
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 3 ms 2792 KB Output is correct
3 Correct 3 ms 2736 KB Output is correct
4 Correct 8 ms 2776 KB Output is correct
5 Correct 6 ms 2900 KB Output is correct
6 Correct 6 ms 2952 KB Output is correct
7 Correct 6 ms 3028 KB Output is correct
8 Correct 6 ms 3284 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3600 KB Output is correct
2 Correct 16 ms 3992 KB Output is correct
3 Correct 14 ms 3968 KB Output is correct
4 Correct 11 ms 4052 KB Output is correct
5 Correct 15 ms 4232 KB Output is correct
6 Correct 18 ms 4408 KB Output is correct
7 Correct 18 ms 5328 KB Output is correct
8 Correct 19 ms 6412 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 16632 KB Output is correct
2 Correct 194 ms 16840 KB Output is correct
3 Correct 428 ms 17420 KB Output is correct
4 Correct 856 ms 18400 KB Output is correct
5 Correct 1179 ms 22312 KB Output is correct
6 Correct 1153 ms 23052 KB Output is correct
7 Correct 1107 ms 22612 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 3 ms 2792 KB Output is correct
3 Correct 3 ms 2736 KB Output is correct
4 Correct 8 ms 2776 KB Output is correct
5 Correct 6 ms 2900 KB Output is correct
6 Correct 6 ms 2952 KB Output is correct
7 Correct 6 ms 3028 KB Output is correct
8 Correct 6 ms 3284 KB Output is correct
9 Correct 11 ms 3600 KB Output is correct
10 Correct 16 ms 3992 KB Output is correct
11 Correct 14 ms 3968 KB Output is correct
12 Correct 11 ms 4052 KB Output is correct
13 Correct 15 ms 4232 KB Output is correct
14 Correct 18 ms 4408 KB Output is correct
15 Correct 18 ms 5328 KB Output is correct
16 Correct 19 ms 6412 KB Output is correct
17 Correct 171 ms 16632 KB Output is correct
18 Correct 194 ms 16840 KB Output is correct
19 Correct 428 ms 17420 KB Output is correct
20 Correct 856 ms 18400 KB Output is correct
21 Correct 1179 ms 22312 KB Output is correct
22 Correct 1153 ms 23052 KB Output is correct
23 Correct 1107 ms 22612 KB Output is correct
24 Correct 1119 ms 25076 KB Output is correct
25 Correct 1127 ms 28076 KB Output is correct
26 Correct 1225 ms 33112 KB Output is correct
27 Correct 1366 ms 38556 KB Output is correct
28 Correct 1601 ms 45932 KB Output is correct
29 Correct 1792 ms 58548 KB Output is correct
30 Correct 1881 ms 71020 KB Output is correct
31 Correct 1882 ms 70812 KB Output is correct
32 Correct 1300 ms 148212 KB Output is correct
33 Correct 1655 ms 25268 KB Output is correct
34 Correct 1924 ms 28464 KB Output is correct
35 Correct 2142 ms 32176 KB Output is correct
36 Correct 3024 ms 52004 KB Output is correct
37 Execution timed out 5090 ms 143164 KB Time limit exceeded
38 Halted 0 ms 0 KB -