Submission #659064

#	Time	Username	Problem	Language	Result	Execution time	Memory
659064		Banan	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	569 ms	152848 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define double long double
#define endl '\n'
#define sz(a) (ll)a.size()
#define pb push_back
#define fs first
#define sc second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()


ll tree[800040], a[200005];

void update(ll v, ll l, ll r, ll pos)
{
    if(l==r)
    {
        tree[v]=a[l];
    }
    else
    {
        ll mid=(l+r)/2;
        if(pos<=mid)
        {
            update(2*v, l, mid, pos);
        }
        else
        {
            update(2*v+1, mid+1, r, pos);
        }
        tree[v]=tree[2*v]+tree[2*v+1];
    }
}

ll ask(ll v, ll l, ll r, ll sl, ll sr)
{
    if(sr<l || sl>r){return 0;}
    if(l==sl && r==sr){return tree[v];}
    ll mid=(l+r)/2;
    ll v1=ask(2*v, l, mid, sl, min(mid, sr));
    ll v2=ask(2*v+1, mid+1, r, max(mid+1, sl), sr);
    return v1+v2;
}

long long count_swaps(vector<int> s) {
    ll n=sz(s);
    map<ll, queue<ll>> m;
    vector<bool> mark(n+5, 0);
    for(ll i=0;i<n;i++)
    {
        m[s[i]].push(i);
    }

    ll ans=0;
    for(ll i=0;i<n;i++)
    {
        if(!mark[i])
        {
            if(s[i]<0)
            {
                ll pos=m[-s[i]].front();
                ll v=ask(1, 1, 2*n, i+1, pos+1);
                ans+=(pos-i-1+v);
                mark[pos]=1;
                mark[i]=1;
                m[-s[i]].pop();
                m[s[i]].pop();
                a[pos+1]=-1;
                update(1, 1, 2*n, pos+1);
            }
            else
            {
                ll pos=m[-s[i]].front();
                ll v=ask(1, 1, 2*n, i+1, pos+1);
                ans+=(pos-i+v);
                mark[pos]=1;
                mark[i]=1;
                m[-s[i]].pop();
                m[s[i]].pop();
                a[pos+1]=-1;
                update(1, 1, 2*n, pos+1);
            }
        }
    }
	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