oj.uz

Submission #1003848

# Submission time Handle Problem Language Result Execution time Memory
1003848 2024-06-20T19:00:17 Z vjudge1 Ekoeko (COCI21_ekoeko) C++17
0 / 110
 256 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> tree;

void update(int pos, int i, int f, int idx){
    if(i == f and i == idx){
        tree[pos]++;
        return;
    }
    int meio = (i+f)/2;
    if(idx <= meio) update(2*pos+1, i, meio, idx);
    else update(2*pos+2, meio+1, f, idx);
    tree[pos] = tree[2*pos+1] + tree[2*pos+2];
    return;
}

int query(int pos, int i, int f, int l, int r){
    if(l<=i and f<=r){
        return tree[pos];
    }
    int meio =(i+f)/2;
    int res = 0;
    if(l <= meio) res += query(2*pos+1, i, meio, l, r);
    if(r > meio) res += query(2*pos+2, meio+1, f, l, r);
    return res;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    vector<vector<int>> letra(30);
    int n; cin >> n;
    n *=2;
    tree.assign(4*(n+1), 0);

    string s; cin >> s;
    

    for(int i=0; i<n; i++){
        int nmr = s[i] - 'a';
        letra[nmr].push_back(i);
    }
    vector<int> qnt(30,0);
    int res = 0;

    for(int i = 0; i<n/2; i++){
        int nmr = s[i] - 'a';
        int sz = letra[nmr].size();
        sz/=2;
        int posicao = letra[nmr][sz + qnt[nmr]];

        res += query(0,0,n,posicao, n);
        update(0,0,n, posicao);
        qnt[nmr]++;
    }

    cout << res << endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 4 ms 2160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 4 ms 2160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 4 ms 2160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 256 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 4 ms 2160 KB Output isn't correct
3 Halted 0 ms 0 KB -