Submission #1114609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114609		lftroq	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	235 ms	273224 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;x-=(x&(-x))) bit[x]+=v;}
int get(int x){int ans=0;for(;x<=n;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();
                x+=get(x);
                //cout << i << ": " << x << ' ' << y << endl;
                ans+=i-x+1;
                update(i+1,1);
                update(x-1,-1);
                qr[s[i]].pop();
            }
        }
        else
        {
            if(ql[s[i]].empty()) qr[s[i]].push(i+1);
            else
            {
                int x=ql[s[i]].front();
                x+=get(x);
                //cout << i << ": " << x << ' ' << y << endl;
                ans+=i-x;
                update(i+1,1);
                update(x-1,-1);
                ql[s[i]].pop();
            }
        }
    }
	return ans;
}

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