Submission #528893

#	Time	Username	Problem	Language	Result	Execution time	Memory
528893		Rafi22	Ekoeko (COCI21_ekoeko)	C++14	110 / 110	11 ms	3648 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=200007;

vector<int>V[200];
int side[N];
int p[N];

int BIT[N];
int que(int x) {
	int s=0;
	for (;x;x-=x&-x) s+=BIT[x];
	return s;
}
void ins(int x,int s) {
	for (;x<=200000;x+=x&-x) BIT[x]+=s;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    s='#'+s;
    for(int i=1;i<=2*n;i++) V[s[i]].pb(i);
    for(int i='a';i<='z';i++)
    {
        for(int j=0;j<sz(V[i])/2;j++) side[V[i][j]]=1;
        for(int j=sz(V[i])/2;j<sz(V[i]);j++) side[V[i][j]]=2;
    }
    ll ans=0,cnt=0;
    for(int i=1;i<=2*n;i++)
    {
        if(side[i]==2)
        {
            cnt++;
            p[i]=cnt;
        }
        else ans+=cnt;
    }
    for(int i='a';i<='z';i++)
    {
        for(int j=0;j<sz(V[i])/2;j++) p[V[i][j]]=p[V[i][j+sz(V[i])/2]];
    }
    for(int i=1;i<=2*n;i++)
    {
        if(side[i]==2) continue;
        ans+=(ll)que(n)-que(p[i]);
        ins(p[i],1);
    }
    cout<<ans;



    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:43:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |     for(int i=1;i<=2*n;i++) V[s[i]].pb(i);
      |                                   ^

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