oj.uz

Submission #515822

# Submission time Handle Problem Language Result Execution time Memory
515822 2022-01-19T20:04:37 Z Victor Ekoeko (COCI21_ekoeko) C++17
110 / 110
 9 ms 2860 KB 
// #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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 1160 KB Output is correct
3 Correct 4 ms 1996 KB Output is correct
4 Correct 7 ms 2728 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 1160 KB Output is correct
3 Correct 4 ms 1996 KB Output is correct
4 Correct 7 ms 2728 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 1160 KB Output is correct
3 Correct 4 ms 1996 KB Output is correct
4 Correct 7 ms 2728 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 8 ms 2588 KB Output is correct
7 Correct 8 ms 2572 KB Output is correct
8 Correct 9 ms 2688 KB Output is correct
9 Correct 8 ms 2656 KB Output is correct
10 Correct 8 ms 2548 KB Output is correct
11 Correct 9 ms 2616 KB Output is correct
12 Correct 8 ms 2516 KB Output is correct
13 Correct 7 ms 2572 KB Output is correct
14 Correct 7 ms 2596 KB Output is correct
15 Correct 8 ms 2696 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 1160 KB Output is correct
3 Correct 4 ms 1996 KB Output is correct
4 Correct 7 ms 2728 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 8 ms 2588 KB Output is correct
11 Correct 8 ms 2572 KB Output is correct
12 Correct 9 ms 2688 KB Output is correct
13 Correct 8 ms 2656 KB Output is correct
14 Correct 8 ms 2548 KB Output is correct
15 Correct 9 ms 2616 KB Output is correct
16 Correct 8 ms 2516 KB Output is correct
17 Correct 7 ms 2572 KB Output is correct
18 Correct 7 ms 2596 KB Output is correct
19 Correct 8 ms 2696 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 0 ms 332 KB Output is correct
22 Correct 0 ms 332 KB Output is correct
23 Correct 0 ms 332 KB Output is correct
24 Correct 0 ms 332 KB Output is correct
25 Correct 0 ms 332 KB Output is correct
26 Correct 0 ms 332 KB Output is correct
27 Correct 0 ms 332 KB Output is correct
28 Correct 0 ms 332 KB Output is correct
29 Correct 0 ms 332 KB Output is correct
30 Correct 0 ms 332 KB Output is correct
31 Correct 0 ms 204 KB Output is correct
32 Correct 8 ms 2860 KB Output is correct
33 Correct 8 ms 2792 KB Output is correct
34 Correct 9 ms 2712 KB Output is correct
35 Correct 8 ms 2732 KB Output is correct
36 Correct 9 ms 2716 KB Output is correct
37 Correct 8 ms 2756 KB Output is correct
38 Correct 9 ms 2720 KB Output is correct
39 Correct 9 ms 2840 KB Output is correct
40 Correct 7 ms 2696 KB Output is correct
41 Correct 8 ms 2596 KB Output is correct