제출 #1131583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131583		duckindog	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	10 ms	2020 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n;
string s;

int bit[N];
inline void upd(int i, int x) { 
  for (; i <= n; i += i & -i) bit[i] += x;
}
inline int que(int i) { 
  int ret = 0;
  for (; i; i -= i & -i) ret += bit[i];
  return ret;
}

int totalCnt[26];
int pos[26][N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  cin >> s;

  s = '@' + s;
  for (int i = 1; i <= 2 * n; ++i) totalCnt[s[i] - 'a'] += 1;

  vector<int> cnt(26);
  { // ranking
    for (int i = 1, it = 0; i <= 2 * n; ++i) { 
      int ch = s[i] - 'a';
      cnt[ch] += 1;
      if (cnt[ch] <= totalCnt[ch] / 2)
        pos[ch][cnt[ch]] = ++it;
    }
  }

  long long answer = 0;
  for (int i = 2 * n; i >= 1; --i) { 
    int ch = s[i] - 'a';
    if (cnt[ch] <= totalCnt[ch] / 2) upd(1, 1);
    else {
      int rank = pos[ch][(cnt[ch] - 1) % (totalCnt[ch] / 2) + 1]; 
      answer += que(rank);
      upd(rank, 1);
    }
    cnt[ch] -= 1;
  }

  cout << answer << "\n";
}

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