Submission #1229541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229541		diana	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	95 ms	37956 KiB

shoes

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

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

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

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

int 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];

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

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

    for(int i=0; i<n; i++)
        add(i, 1);

    ll ans = 0;

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

    return ans;
}

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