oj.uz

Submission #1003799

# Submission time Handle Problem Language Result Execution time Memory
1003799 2024-06-20T17:56:57 Z vjudge1 Ekoeko (COCI21_ekoeko) C++17
20 / 110
 12 ms 4824 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxa = 30;
const int maxn = 1e5 + 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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 5 ms 1756 KB Output is correct
3 Runtime error 12 ms 4824 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 5 ms 1756 KB Output is correct
3 Runtime error 12 ms 4824 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 5 ms 1756 KB Output is correct
3 Runtime error 12 ms 4824 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 0 ms 872 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 860 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 5 ms 1756 KB Output is correct
3 Runtime error 12 ms 4824 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -