Submission #204759

#	Time	Username	Problem	Language	Result	Execution time	Memory
204759		T0p_	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	9 ms	5112 KiB

shoes

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

int fw[200200], mark[200200]; 
vector<int> L[100100], R[100100];

void update(int pos, int sz, int val)
{
	while(pos <= sz)
	{
		fw[pos] += val;
		pos += -pos&pos;
	}
}

int query(int pos)
{
	int sum = 0;
	while(pos)
	{
		sum += fw[pos];
		pos -= -pos&pos;
	}
	return sum;
}

long long count_swaps(vector<int> arr)
{
    int n = arr.size();
    for(int i=0 ; i<n ; i++)
    {
    	if(arr[i] < 0) L[abs(arr[i])].pb(i+1);
    	else R[abs(arr[i])].pb(i+1);
    	update(i+1, n, 1);
    }
    long long ans = 0;
    for(int i=0 ; i<n ; i++)
    {
    	if(mark[i]) continue ;
    	int d = abs(arr[i]);
    	if(arr[i] < 0)
    	{
    		int l = 0, r = R[d].size() - 1;
    		while(l!=r)
    		{
    			int mid = (l+r)>>1;
    			if(R[d][mid] > i) r = mid;
    			else l = mid+1;
    		}
    		ans += query(R[d][l]) - 2;
    		update(i+1, n, -1);
    		update(R[d][l], n, -1);
    		mark[i] = mark[R[d][l]-1] = 1;
    	}	
    	else
    	{
    		int l = 0, r = L[d].size()-1;
    		while(l!=r)
    		{
    			int mid = (l+r)>>1;
    			if(L[d][mid] > i) r = mid;
    			else l = mid+1;
    		}
    	    ans += query(L[d][l]) - 1;
    		update(i+1, n, -1);
    		update(L[d][l], n, -1);
    		mark[i] = mark[L[d][l]-1] = 1;
    	}
    }
    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