Submission #1325999

#TimeUsernameProblemLanguageResultExecution timeMemory
1325999hyyhGroup Photo (JOI21_ho_t3)C++20
0 / 100
1 ms332 KiB
#include <iostream>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <iomanip>
#include <set>
#include <bitset>

#define int long long

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using piii = tuple<int,int,int>;
#define endl '\n'
#define f first
#define s second


int const N = 1e6+10;

int fenwick[N];
int si;

void add(int id){
    for (;id <= si;id += id&-id) fenwick[id] += 1;
}

int sum(int id){
    int sum = 0;
    for (;id > 0;id -= id&-id) sum += fenwick[id];
    return sum;
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin >> n;
    string st1;
    string st2;
    cin >> st1 >> st2;
    queue<int> mp[28];
    vector<int> vc;
    for(int i{};i < n;i++){
        mp[st1[i]-'A'].emplace(i);
    }
    for(int i{};i < n;i++){
        vc.emplace_back(mp[st2[i]-'A'].front());
        mp[st2[i]-'A'].pop();
    }
    int ans = 0;
    si = pow(2,ceil(log2(n)));
    for(int i{};i < n;i++){
        ans += i-sum(vc[i]+1);
        add(vc[i]+1);
    }
    cout << ans;
}
#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...