oj.uz

Submission #157686

# Submission time Handle Problem Language Result Execution time Memory
157686 2019-10-12T17:40:06 Z lukameladze Arranging Shoes (IOI19_shoes) C++14
0 / 100
 918 ms 1048580 KB 
# include <bits/stdc++.h>
using namespace std;
long long n,a[200005],pas,tree[200005],ans,w,w1,fix[200005];
queue <long long> q[10][200005];
void inc (long long ind,long long val)
{
    for (long long 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[1][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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 918 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 918 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 918 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 876 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 918 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 918 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -