제출 #157685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
157685		lukameladze	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	50 ms	20188 KiB

shoes

# include <bits/stdc++.h>
using namespace std;
long long n,a[100005],pas,tree[100005],ans,w,w1,fix[100005];
queue <long long> q[10][1005];
void inc (long long ind,long long val)
{
    for (int i=ind; i<=2*n;  i+=(i&(-i)))
    {
        tree[i]+=val;
    }
}
long long sum (long long ind)
{
    pas=0;
    for (int i=ind; i>0; i-=(i&(-i)))
    pas+=tree[i];
    
    return pas;
}
long long count_swaps(std::vector <int> v)
{
	n=v.size()/2;
	for (long long i=1; i<=2*n; i++)
	{
		a[i]=v[i-1];
	}
	for (long long  i=1; i<=2*n; i++)
	{
		inc(i,1);
	}
	for(long long i=1; i<=2*n; i++)
	{
	    if (a[i]>=0)
		{
			w=a[i];
			if (q[0][a[i]].size()==0)
			{
				q[1][a[i]].push(i);
				//inc(q[2][a[i]].front(),1);
			}
			else
			{
				ans+=sum(i-1)-sum(q[0][a[i]].front()-1)-1;
				inc(q[0][a[i]].front(),1);
				inc(i,-1);
				q[0][a[i]].pop();
			}
		}	
			else
			{
			 	if (q[1][-a[i]].size()==0)
				{
				 	q[0][-a[i]].push(i);
				// 	inc(q[1][-a[i]].front(),1);
				}   
				else
				{
				ans+=sum(i-1)-sum(q[1][-a[i]].front()-1);
			//	ans++;
				inc(q[1][-a[i]].front(),1);
				inc(i,-1);
				q[1][-a[i]].pop();
				}
			}
	}
	return ans;
}

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