Submission #370562

#	Time	Username	Problem	Language	Result	Execution time	Memory
370562		Fysty	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	99 ms	15084 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define F first
#define S second
#define pb push_back
const int N=1e5+5;
vector<ll> l[N],r[N];
bool vis[N<<1];
int bit[N<<1];
int sz;
void add(int pos,int val)
{
    for(int i=pos;i<=sz;i+=i&-i) bit[i]+=val;
}
ll qry(int pos)
{
    ll ret=0;
    for(int i=pos;i>=1;i-=i&-i) ret+=bit[i];
    return ret;
}
ll count_swaps(vector<int> S)
{
    ll n=S.size()/2;
    sz=2*n;
    for(int i=2*n-1;i>=0;i--)
    {
        if(S[i]<0) l[-S[i]].pb(i);
        else r[S[i]].pb(i);
    }
    ll ans=0;
    rep(i,2*n)
    {
        if(vis[i]) continue;
        vis[i]=1;
        ll id;
        if(S[i]>0)
        {
            r[S[i]].pop_back();
            id=l[S[i]].back();
            l[S[i]].pop_back();
            ans++;
        }
        else
        {
            l[-S[i]].pop_back();
            id=r[-S[i]].back();
            r[-S[i]].pop_back();
        }
        vis[id]=1;
        ans+=id-i-1-(qry(id)-qry(i+1));
        add(id+1,1);
        //cout<<ans<<"\n";
    }
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15