Submission #1114600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114600		lftroq	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1073 ms	138056 KiB

shoes

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

#define fi first
#define se second
const int N=100005;

int n;
queue<pair<int,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,get(i+1)});
                update(i+1,1);
            }
            else
            {
                int x=qr[s[i]].front().fi,y=qr[s[i]].front().se;
                //cout << i << ": " << x << ' ' << y << endl;
                ans+=i-x+1-y;
                update(x,-1);
                qr[s[i]].pop();
            }
        }
        else
        {
            if(ql[s[i]].empty())
            {
                qr[s[i]].push({i+1,get(i+1)});
                update(i+1,1);
            }
            else
            {
                int x=ql[s[i]].front().fi,y=ql[s[i]].front().se;
                //cout << i << ": " << x << ' ' << y << endl;
                ans+=i-x-y;
                update(x,-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