Submission #922352

#	Time	Username	Problem	Language	Result	Execution time	Memory
922352		Shayan86	Ekoeko (COCI21_ekoeko)	C++14	110 / 110	18 ms	5668 KiB

Main

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

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll A = 28;
const ll N = 2e5 + 50;
const ll Mod = 1e9 + 7;

ll n, num[N], ps[N];

string s, t1, t2;
vector<int> idx[A];

int bit[N];

void upd(int x, int y){
    for(; x <= n; x += x & (-x)) bit[x] += y;
}

int get(int x){
    ll out = 0;
    for(; x; x &= x-1) out += bit[x];
    return out;
}

int main(){
    fast_io;

    cin >> n >> s;
    s = "$" + s;

    for(int i = 0; i < A; i++){
        int cnt = 0, c = 0;
        for(int j = 1; j <= 2*n; j++) if(s[j] - 'a' == i) cnt++;
        for(int j = 1; j <= 2*n; j++) if(s[j] - 'a' == i) num[j] = ((++c) <= cnt/2 ? 1 : 2);
    }

    ll sum = 0;
    for(int i = 1; i <= 2*n; i++) ps[i] = ps[i-1] + num[i] - 1;
    for(int i = 1; i <= 2*n; i++) sum += ps[i] * (num[i] == 1);

    t1 = t2 = "$";
    for(int i = 1; i <= 2*n; i++){
        if(num[i] == 1) t1 += s[i];
        else t2 += s[i];
    }

    for(int i = 0; i < A; i++){
        for(int j = n; j > 0; j--) if(t2[j] - 'a' == i) idx[i].pb(j);
    }

    for(int i = 1; i <= n; i++){
        upd(idx[t1[i] - 'a'].back(), 1); sum += idx[t1[i] - 'a'].back() - get(idx[t1[i] - 'a'].back());
        idx[t1[i] - 'a'].pop_back();
    }

    cout << sum;

}

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