oj.uz

Submission #639091

# Submission time Handle Problem Language Result Execution time Memory
639091 2022-09-08T14:33:31 Z LeonaRaging Swap Swap Sort (CCO21_day1problem1) C++14
25 / 25
 926 ms 58352 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 4;
const int INF = 1e9;
const int block = 100;
const int N = 1e6 + 4;

struct seg_tree {
    vector<int> t;
    seg_tree() {
        t.resize(4 * maxn);
    }
    void update(int pos, int v = 1, int l = 1, int r = maxn - 1) {
        if (l == r) {
            t[v]++;
            return;
        }
        int m = (l + r) / 2;
        if (pos <= m) update(pos, 2 * v, l, m);
        else update(pos, 2 * v + 1, m + 1, r);
        t[v] = t[2 * v] + t[2 * v + 1];
    }
    int get(int l, int r, int v = 1, int tl = 1, int tr = maxn - 1) {
        if (tl > r || tr < l) return 0;
        if (tl >= l && tr <= r) return t[v];
        int m = (tl + tr) / 2;
        int L = get(l, r, 2 * v, tl, m);
        int R = get(l, r, 2 * v + 1, m + 1, tr);
        return L + R;
    }
} IT;

int n, k, q, a[maxn], p[maxn], sum[maxn], delta[N];
vector<int> pos[maxn];
vector<pair<int,int>> adj[maxn];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> k >> q;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        res += IT.get(a[i] + 1, n);
        pos[a[i]].pb(i);
        IT.update(a[i]);
    }
    for (int i = 1; i <= n; i++)
        p[i] = i;
    for (int i = 1; i <= q; i++) {
        int j; cin >> j;
        int x = p[j], y = p[j + 1];
        if (pos[x].size() <= block && pos[y].size() <= block) {
            int l = 0, inv = 0;
            for (int r = 0; r < (pos[x].size()); r++) {
                while (l + 1 < (pos[y].size()) && pos[y][l + 1] < pos[x][r])
                    l++;
                if (l < (pos[y].size()) && pos[y][l] < pos[x][r])
                    inv += l + 1;
            }
            delta[i] = -2 * inv + pos[x].size() * pos[y].size();
        }
        else {
            if (pos[x].size() > block) adj[x].pb({y, i});
            else adj[y].pb({x, -i});
        }
        swap(p[j], p[j + 1]);
    }
    for (int x = 1; x <= n; x++) {
        if (pos[x].size() <= block) continue;
        memset(sum, 0, sizeof sum);
        for (auto i : pos[x])
            sum[i] = 1;
        for (int i = 1; i <= n; i++)
            sum[i] += sum[i - 1];
        sort(adj[x].begin(), adj[x].end());
        int i = 0;
        while (i < (adj[x].size())) {
            int y = adj[x][i].fi, inv = pos[x].size() * pos[y].size();
            for (int j : pos[y])
                inv -= sum[j];
            inv = -2 * inv + pos[x].size() * pos[y].size();
            while (adj[x][i].fi == y && i < (adj[x].size())) {
                if (adj[x][i].se > 0) delta[adj[x][i].se] = inv;
                else delta[-adj[x][i].se] = -inv;
                i++;
            }
        }
    }
    for (int i = 1; i <= q; i++)
        res += delta[i], cout << res << '\n';
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:67:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for (int r = 0; r < (pos[x].size()); r++) {
      |                             ~~^~~~~~~~~~~~~~~~~
Main.cpp:68:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |                 while (l + 1 < (pos[y].size()) && pos[y][l + 1] < pos[x][r])
      |                        ~~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:70:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                 if (l < (pos[y].size()) && pos[y][l] < pos[x][r])
      |                     ~~^~~~~~~~~~~~~~~~~
Main.cpp:90:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         while (i < (adj[x].size())) {
      |                ~~^~~~~~~~~~~~~~~~~
Main.cpp:95:43: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             while (adj[x][i].fi == y && i < (adj[x].size())) {
      |                                         ~~^~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 7 ms 9300 KB Output is correct
3 Correct 6 ms 9300 KB Output is correct
4 Correct 8 ms 9300 KB Output is correct
5 Correct 10 ms 8328 KB Output is correct
6 Correct 6 ms 8404 KB Output is correct
7 Correct 7 ms 8348 KB Output is correct
8 Correct 10 ms 8340 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 11532 KB Output is correct
2 Correct 34 ms 11332 KB Output is correct
3 Correct 66 ms 11680 KB Output is correct
4 Correct 169 ms 11584 KB Output is correct
5 Correct 47 ms 11076 KB Output is correct
6 Correct 53 ms 11056 KB Output is correct
7 Correct 58 ms 11472 KB Output is correct
8 Correct 68 ms 11728 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 46716 KB Output is correct
2 Correct 252 ms 48340 KB Output is correct
3 Correct 275 ms 48884 KB Output is correct
4 Correct 292 ms 52660 KB Output is correct
5 Correct 392 ms 58088 KB Output is correct
6 Correct 453 ms 54120 KB Output is correct
7 Correct 454 ms 54296 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 7 ms 9300 KB Output is correct
3 Correct 6 ms 9300 KB Output is correct
4 Correct 8 ms 9300 KB Output is correct
5 Correct 10 ms 8328 KB Output is correct
6 Correct 6 ms 8404 KB Output is correct
7 Correct 7 ms 8348 KB Output is correct
8 Correct 10 ms 8340 KB Output is correct
9 Correct 40 ms 11532 KB Output is correct
10 Correct 34 ms 11332 KB Output is correct
11 Correct 66 ms 11680 KB Output is correct
12 Correct 169 ms 11584 KB Output is correct
13 Correct 47 ms 11076 KB Output is correct
14 Correct 53 ms 11056 KB Output is correct
15 Correct 58 ms 11472 KB Output is correct
16 Correct 68 ms 11728 KB Output is correct
17 Correct 209 ms 46716 KB Output is correct
18 Correct 252 ms 48340 KB Output is correct
19 Correct 275 ms 48884 KB Output is correct
20 Correct 292 ms 52660 KB Output is correct
21 Correct 392 ms 58088 KB Output is correct
22 Correct 453 ms 54120 KB Output is correct
23 Correct 454 ms 54296 KB Output is correct
24 Correct 652 ms 50644 KB Output is correct
25 Correct 744 ms 34568 KB Output is correct
26 Correct 423 ms 35028 KB Output is correct
27 Correct 332 ms 35276 KB Output is correct
28 Correct 292 ms 35988 KB Output is correct
29 Correct 284 ms 36536 KB Output is correct
30 Correct 280 ms 37100 KB Output is correct
31 Correct 268 ms 37024 KB Output is correct
32 Correct 237 ms 55412 KB Output is correct
33 Correct 406 ms 58352 KB Output is correct
34 Correct 416 ms 55616 KB Output is correct
35 Correct 453 ms 54776 KB Output is correct
36 Correct 665 ms 50036 KB Output is correct
37 Correct 741 ms 35872 KB Output is correct
38 Correct 577 ms 34960 KB Output is correct
39 Correct 273 ms 36980 KB Output is correct
40 Correct 272 ms 42416 KB Output is correct
41 Correct 278 ms 45552 KB Output is correct
42 Correct 300 ms 53388 KB Output is correct
43 Correct 304 ms 53624 KB Output is correct
44 Correct 279 ms 53980 KB Output is correct
45 Correct 307 ms 55376 KB Output is correct
46 Correct 439 ms 36564 KB Output is correct
47 Correct 579 ms 36180 KB Output is correct
48 Correct 926 ms 36664 KB Output is correct
49 Correct 812 ms 36264 KB Output is correct
50 Correct 304 ms 53168 KB Output is correct
51 Correct 255 ms 53188 KB Output is correct
52 Correct 260 ms 52448 KB Output is correct
53 Correct 275 ms 53372 KB Output is correct
54 Correct 279 ms 53452 KB Output is correct
55 Correct 5 ms 8148 KB Output is correct