oj.uz

답안 #157683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
157683 2019-10-12T17:35:09 Z lukameladze Arranging Shoes (IOI19_shoes) C++14
0 / 100
 9 ms 7032 KB 
# 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);
				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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7032 KB Output isn't correct
2 Halted 0 ms 0 KB -