제출 #867118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867118		epicci23	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	11 ms	3816 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

constexpr int N = 1e5 + 5;
int fw[N];

void upd(int c){
  for(;c<N;c+=c&-c) fw[c]++;
}

int query(int c,int res=0){
  for(;c;c-=c&-c) res+=fw[c];
  return res;
}

vector<int> convert(string a,string b,int n){
  queue<int> q[26];
  for(int i=0;i<n;i++) q[b[i]-'a'].push(i);
  
  vector<int> res;

  for(int i=0;i<n;i++){
    res.pb(q[a[i]-'a'].front()+1);
    q[a[i]-'a'].pop();
  }

  return res;
}

void solve(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  string s1="",s2="";
 
  int cnt[26],cur[26];
  for(int i=0;i<26;i++) cnt[i]=count(all(s),(char)('a'+i)); 
  int ans=0,c2=0;
  memset(cur,0,sizeof(cur));
  for(int i=0;i<2*n;i++){
    cur[s[i]-'a']++;
    if(cur[s[i]-'a']>cnt[s[i]-'a']/2){ 
      c2++;
      s2.pb(s[i]);
    }
    else{ 
      ans+=c2;
      s1.pb(s[i]);
    }
  }

  vector<int> perm = convert(s1,s2,n);
  
  for(int i=0;i<n;i++){
  	ans+=query(n)-query(perm[i]);
  	upd(perm[i]);
  }

  cout << ans << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

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