Submission #755558

#	Time	Username	Problem	Language	Result	Execution time	Memory
755558		Rafi22	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	273 ms	274328 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=200007;

int BIT[N];
bool is[N];
deque<int>V[2*N];

void ins(int v,int x)
{
    for(;v<N;v+=v&(-v)) BIT[v]+=x;
}
int que(int v)
{
    int ans=0;
    for(;v>0;v-=v&(-v)) ans+=BIT[v];
    return ans;
}


ll count_swaps(vector<int>s)
{
    int n=sz(s);
    for(int i=1;i<=n;i++)
    {
        ins(i,1);
        is[i]=1;
        V[s[i-1]+N].pb(i);
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(!is[i]) continue;
        int p=V[-s[i-1]+N][0];
        V[-s[i-1]+N].pop_front();
        V[s[i-1]+N].pop_front();
        ins(i,-1);
        ins(p,-1);
        ans+=que(p);
        is[p]=0;
        if(s[i-1]>0) ans++;
    }
    return ans;
}
/*
int main()
{
    cout<<count_swaps({-2, 2, 2, -2, -2, 2})<<endl;
    return 0;
}*/

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