oj.uz

Submission #767727

# Submission time Handle Problem Language Result Execution time Memory
767727 2023-06-27T05:54:25 Z drdilyor Ekoeko (COCI21_ekoeko) C++17
0 / 110
 1 ms 468 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Fenwick {
    int n;
    vector<int> t;
    Fenwick (int n) : n(n), t(n) {}
    void inc(int i, int d=1) {
        for (; i < n; i |= i+1)
            t[i] += d;
    }
    int sum(int r) {
        int s = 0;
        for (; r >= 0; r = (r&(r+1))-1)
            s += t[r];
        return s;
    }
};

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    string s;
    cin >> n >> s;
    string t = s;
    sort(t.begin(), t.begin() + n);
    sort(t.begin() + n, t.end());
    assert(t.substr(0, n) == t.substr(n, n));

    vector<int> arr(n);
    vector<vector<int>> ix(128);
    for (int i = 0; i < n; i++)
        ix[s[i]].push_back(i);
    for (auto& i : ix) reverse(i.begin(), i.end());

    for (int i = 0; i < n; i++) {
        arr[i] = ix[s[i+n]].back();
        ix[s[i+n]].pop_back();
    }

    Fenwick tree(n);
    ll res = 0;
    for (int i = 0; i < n; i++) {
        res += i - tree.sum(arr[i]-1);
        tree.inc(arr[i]);
    }
    cout << res << endl;

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -