Submission #428061

#	Time	Username	Problem	Language	Result	Execution time	Memory
428061		MOUF_MAHMALAT	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	407 ms	282544 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
deque<ll>v[200009],w[200009];
ll ans,x,y,op,p[800009],lz[800009],n;
bool b[200009];
void push(ll d,ll l,ll r)
{
    p[d]+=lz[d];
    if(l<r)
    {
        lz[d*2]+=lz[d];
        lz[d*2+1]+=lz[d];
    }
    lz[d]=0;
}
void up(ll d,ll l,ll r,ll xx,ll yy)
{
    push(d,l,r);
    if(r<xx||l>yy||xx>yy)
        return;
    if(xx<=l&&yy>=r)
    {
        lz[d]++;
        return;
    }
    ll m=(l+r)/2,i=d*2;
    up(i,l,m,xx,yy),up(i+1,m+1,r,xx,yy);
}
ll best(ll d,ll l,ll r,ll id)
{
    push(d,l,r);
    if(l==r)
        return p[d];
    ll m=(l+r)/2,i=d*2;
    if(id<=m)
        return best(i,l,m,id);
    else
        return best(i+1,m+1,r,id);
}
long long count_swaps(vector<int> s)
{
    n=s.size()-1;
    for(ll i=0; i<=n; i++)
    {
        if(s[i]>0)
            v[s[i]].push_back(i);
        else
            w[-s[i]].push_back(i);
    }
    for(ll i=0; i<=n; i++)
    {
        if(b[i])
            continue;
        if(v[abs(s[i])].empty())
            continue;
        if(s[i]>0)
        {
            x=v[s[i]].front();
            y=w[s[i]].front();
            ans++;
        }
        else
        {
            x=w[-s[i]].front();
            y=v[-s[i]].front();
        }
        b[x]=b[y]=1;
        v[abs(s[i])].pop_front();
        w[abs(s[i])].pop_front();
        ans+=y+best(1,0,n,y)-x-best(1,0,n,x)-1;
        up(1,0,n,x+1,y);
    }
    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