제출 #815912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
815912		kebine	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	14 ms	3928 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 2e5 + 5;
int N;
string S;
int curCnt[26], totCnt[26], pos[26][MX];
vector<int> a;

struct fw {
      int t[MX];
      void upd(int x, int val) {
            for(int i = x; i <= N; i += i & -i) t[i] += val;
      } 
      int que(int x) {
            int res = 0;
            for(int i = x; i > 0; i -= i & -i) res += t[i];
            return res;
      }
      int que(int l, int r) {
            return que(r) - que(l - 1);
      }

      void reset() {
            for(int i = 0; i < MX; i++) t[i] = 0;
      }
} ft;

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      cin >> N >> S;
      for(auto x : S) a.push_back(x - 'a');

      for(auto x : a)
            totCnt[x]++;

      int i = 0, r = 0;
      vector<pair<int,int>> v;

      ll ans = 0;
      for(auto x : a) {
            if(curCnt[x] < totCnt[x] / 2) {
                  pos[x][curCnt[x]] = i;
                  ans += r;
            } else {
                  pos[x][curCnt[x]] = i;
                  v.push_back({pos[x][curCnt[x] - totCnt[x] / 2], r});
                  r++;
            }
            curCnt[x]++;
            i++;
      }

      sort(v.begin(), v.end());

      ft.reset();

      for(auto [l, r] : v) {
            ans += ft.que(r + 1, N);
            ft.upd(r + 1, 1);
      }      

      cout << ans << '\n';

}

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