Submission #515822

#	Time	Username	Problem	Language	Result	Execution time	Memory
515822		Victor	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	9 ms	2860 KiB

Main

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

struct fenwick_tree {
    vll ft;
    fenwick_tree(ll n) {
        ft.assign(n+1,0);
    }

    ll rsq(ll i) {
        ll sum=0;
        for(;i;i-=i&-i) sum+=ft[i];
        return sum;
    }

    ll rsq(ll i,ll j) {return rsq(j)-rsq(i-1);}

    void update(ll i,ll v) {
        for(;i<sz(ft);i+=i&-i) ft[i]+=v;
    }
};

ll cnt[150],n,ans=0;
vll lets[150];
string word;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    memset(cnt,0,sizeof(cnt));
    cin>>n>>word;

    trav(let,word) ++cnt[let];
    rep(i,0,150) cnt[i]/=2;

    string p1="",p2="";
    trav(let,word) {
        if(cnt[let]) {
            --cnt[let];
            p1+=let;
            ans+=sz(p2);

        } else {
            p2+=let;
            lets[let].pb(sz(p2));
        }
    }

    word=p1+p2;
    //cout<<word<<endl;
    rep(i,0,150) reverse(all(lets[i]));

    fenwick_tree fenwick(n);
    ll target=1;
    trav(let,p1) {
        int pos=lets[let].back();
        lets[let].pop_back();
        fenwick.update(pos,1);
        pos+=fenwick.rsq(pos+1, n);

        //cout<<"let = "<<let<<" pos = "<<pos<<" target = "<<target<<endl;
        ans+=pos-target;
        assert(pos>=target);
        ++target;
    }

    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void fenwick_tree::update(ll, ll)':
Main.cpp:48:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(;i<sz(ft);i+=i&-i) ft[i]+=v;
      |               ^
Main.cpp: In function 'int main()':
Main.cpp:63:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   63 |     trav(let,word) ++cnt[let];
      |                          ^~~
Main.cpp:68:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   68 |         if(cnt[let]) {
      |                ^~~
Main.cpp:69:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   69 |             --cnt[let];
      |                   ^~~
Main.cpp:75:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   75 |             lets[let].pb(sz(p2));
      |                  ^~~
Main.cpp:86:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   86 |         int pos=lets[let].back();
      |                      ^~~
Main.cpp:87:14: warning: array subscript has type 'char' [-Wchar-subscripts]
   87 |         lets[let].pop_back();
      |              ^~~

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