Submission #1003801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003801		vjudge1	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	20 ms	4028 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxa = 30;
const int maxn = 2e5 + 10;

vector<int> bit(maxn), ocorrencias[maxa];

void update( int id, int val ){ for( int i = id; i < maxn; i += i&-i ) bit[i] += val; }
int query( int id ){ int sum = 0; for( int i = id; i > 0; i -= i&-i ) sum += bit[i]; return sum; }

int main(){
  int n; cin >> n;
  for( int i = 1; i <= 2*n; i++ ){
    char c; cin >> c;
    ocorrencias[c - 'a'].push_back(i);
  }
  vector<pair<int, int>> original;
  for( int i = 0; i < 26; i++ ) for( int j = 0; j < ocorrencias[i].size()/2; j++ ) original.push_back({ ocorrencias[i][j], i });
  sort( original.begin(), original.end() );
  vector<int> cont(maxa), v(2*n + 1);
  for( int i = 0; i < original.size(); i++){
    int letra = original[i].second;
    v[ocorrencias[letra][cont[letra]]] = i + 1;
    v[ocorrencias[letra][cont[letra] + ocorrencias[letra].size()/2]] = n + i + 1;
    cont[letra]++;
  }

  ll resp = 0;
  for( int i = 1; i <= 2*n; i++ ){
    update(v[i], 1);
    int inversoes = i - query(v[i]);
    resp += inversoes;
  }
  cout << resp << endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:19:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for( int i = 0; i < 26; i++ ) for( int j = 0; j < ocorrencias[i].size()/2; j++ ) original.push_back({ ocorrencias[i][j], i });
      |                                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for( int i = 0; i < original.size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~

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