Submission #1114615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114615		lftroq	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	239 ms	273736 KiB

shoes

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

const int N=200005;

int n;
queue<int> ql[N],qr[N];
int bit[N];

void update(int x,int v){for(;x<=n;x+=(x&(-x))) bit[x]+=v;}
int get(int x){int ans=0;for(;x;x-=(x&(-x))) ans+=bit[x];return ans;}

long long count_swaps(std::vector<int> s) {
    ll ans=0;
    n=(int)s.size();
    for(int i=0;i<(int)s.size();i++)
    {
        if(s[i]<0)
        {
            s[i]*=-1;
            if(qr[s[i]].empty()) ql[s[i]].push(i+1);
            else
            {
                int x=qr[s[i]].front();
                int temp=get(x);
                ans+=i-x+1-temp;
                update(x,1);
                update(i+2,-1);
                qr[s[i]].pop();
            }
        }
        else
        {
            if(ql[s[i]].empty()) qr[s[i]].push(i+1);
            else
            {
                int x=ql[s[i]].front();
                int temp=get(x);
                ans+=i-x-temp;
                update(x,1);
                update(i+2,-1);
                ql[s[i]].pop();
            }
        }
    }
	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