제출 #1163496

#제출 시각아이디문제언어결과실행 시간메모리
1163496justin271828Ekoeko (COCI21_ekoeko)C++20
0 / 110
1096 ms1352 KiB
#include <bits/stdc++.h>
using namespace std;

#define l2 long long

int n;
l2 ft[123456];

void up(int x, l2 k) {
    while (x <= (l2)n) {
        ft[x] += k;
        x += (x & (-x));
    } 
}

l2 q(int x) {
    l2 ans = 0;
    while (x > 0) {
        ans += ft[x];
        x -= (x & (-x));
    }
    return ans;
}

int main() {
    cin >> n;
    string s;
    cin >> s;
    queue<int> v[26];
    for (int i = 0; i < n; i++) v[s[n+i]-97].push(i+1);
    l2 ans = 0;
    memset(ft, 0, sizeof(ft));
    for (int i = 1; i <= n; i++) up(i, 1);
    for (int i = 0; i < n; i++) {
        ans += q(v[s[i]-97].front()-1);
        up(v[s[i]-97].front(), -1);
        v[s[i]-97].pop();
    }
    cout << ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...