제출 #303827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
303827		noob_c0de	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	118 ms	19064 KiB

shoes

#include<bits/stdc++.h>
using namespace std;
#define ar array
const int mxn=2e5+3;
int n;
vector<int> pos[mxn],neg[mxn];
int ft[2*mxn];
int vis[mxn];
void upd(int u,int d)
{
    while(u<=n)
    {
        ft[u]+=d;
        u+=u&-u;
    }
}
int get(int u)
{
    int res=0;
    while(u)
    {
        res+=ft[u];
        u-=u&-u;
    }
    return res;
}
int count_swaps(vector<int> a)
{
    n=a.size();
    for (int i=n;i>=1;i--)
    {
        if (a[i-1]>0) pos[a[i-1]].push_back(i);
        else neg[-a[i-1]].push_back(i);
    }
    long long ans=0;
    for (int i=1;i<=n;i++)
    if (!vis[i])
    {
        int vt;
        if (a[i-1]>0) vt=neg[a[i-1]].back();
        else vt=pos[-a[i-1]].back();
        pos[abs(a[i-1])].pop_back();
        neg[abs(a[i-1])].pop_back();
        ans+=(vt+get(vt))-(i+get(i))-1;
        if (a[i-1]>0) ans++;
        upd(1,1);
        if (vt+1<=n) upd(vt+1,-1);
        vis[vt]=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