Submission #1229562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229562		diana	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	107 ms	31140 KiB

shoes

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

const int N = 8e5+5;
ll st[N], n=0;

void add(int i, ll x, int l=0, int r=n, int cur=1)
{
    st[cur] += x;
    if(l == r)
        return;

    ll mid = (l+r)/2;
    if(i <= mid)
        add(i, x, l, mid, 2*cur);
    else
        add(i, x, mid+1, r, 2*cur+1);
}

ll cnt(int lg, int rg, int l=0, int r=n, int cur=1)
{
    if(rg < lg)
        return 0;
    if(rg < l || r < lg)
        return 0;
    if(lg <= l && r <= rg)
        return st[cur];

    ll mid = (l+r)/2;
    return cnt(lg, rg, l, mid, 2*cur) + cnt(lg, rg, mid+1, r, 2*cur+1);
}
vector<int> p[N];

int m;

ll count_swaps(vector<int> s)
{
    n = s.size();
    m = n + 5;
    for(int i=n-1; i>=0; i--)
        p[m+s[i]].push_back(i),
        add(i, 1);

    ll ans = 0;

    for(int i=0; i<n; i++)
    {
        if(cnt(i, i) == 0)
            continue;
        ll pa = -s[i];
        ll id = p[m+pa].back();
        p[m+pa].pop_back();
        p[m-pa].pop_back();
        add(i, -1);
        add(id, -1);
        ans += cnt(i, id);
        if(s[i] > 0)
            ans++;
    }

    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