Submission #1003894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003894		vjudge1	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	24 ms	9192 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
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;
}

signed 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);
    }

    string inicio = "", fim = "";
    vector<int> qnt(30,0);
    int esq = 0, dir = 0;
    
    int res = 0;

    for(int i=0; i<n; i++){
        int nmr = s[i] - 'a';

        if(i<n/2){
            if(qnt[nmr]< (letra[nmr].size()/2)){
                inicio+=s[i];
            }
            else{
                fim += s[i];
                dir++;
            }
        }
        else{
            if(qnt[nmr]< (letra[nmr].size()/2)){
                inicio+=s[i];
                esq++;
            }
            else{
                fim += s[i];
            }
        }
        qnt[nmr]++;
    }

    res += dir*esq;

    int ii= 0, ff = 0;
    qnt.assign(30,0);

    for(int i=0; i<n; i++){
        int nmr = s[i] - 'a';

        if(i<n/2){
            if(qnt[nmr]>= (letra[nmr].size()/2)){
                res += (n/2-1 - (dir-ii) + 1 - i);
                ii++;
            }
        }
        else{
            if(qnt[nmr]< (letra[nmr].size()/2)){
                res += (i - (n/2 + ff));
                ff++;
            }
        }
        qnt[nmr]++;
    }


    s = inicio + fim;

    for(int i=0; i<30; i++) letra[i].clear();

    for(int i=0; i<n; i++){
        int nmr = s[i] - 'a';
        letra[nmr].push_back(i);
    }

    qnt.assign(30,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;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:56:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             if(qnt[nmr]< (letra[nmr].size()/2)){
Main.cpp:65:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             if(qnt[nmr]< (letra[nmr].size()/2)){
Main.cpp:85:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             if(qnt[nmr]>= (letra[nmr].size()/2)){
Main.cpp:91:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             if(qnt[nmr]< (letra[nmr].size()/2)){

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40