Submission #162850

#	Time	Username	Problem	Language	Result	Execution time	Memory
162850		fluffypotato	Arranging Shoes (IOI19_shoes)	Java	100 / 100	681 ms	82552 KiB

shoes

import java.util.ArrayList;
import java.util.*;

public class shoes {
	public long count_swaps(int[] s) {
		int n=s.length;
		PriorityQueue<Integer>pos[]=new PriorityQueue[n];
		PriorityQueue<Integer>neg[]=new PriorityQueue[n];
		for(int i=0;i<n;i++){
			pos[i]=new PriorityQueue<>();
			neg[i]=new PriorityQueue<>();

			update(i,1,220000);
		}
		for(int i=0;i<n;i++){
			if(s[i]>0){
				pos[s[i]].add(i);
			}
			else{
				neg[-1*s[i]].add(i);
			}
		}
//		for(int i=0;i<n;i++){
//			Collections.sort(pos[i]);
//		}
		long ans=0;
		boolean[]visited=new boolean[n];
		for(int i=0;i<n;i++){
			if(!visited[i]){
				if(s[i]>0){
					visited[i]=true;
					pos[s[i]].poll();
					int idx=neg[s[i]].poll();
					visited[idx]=true;
					long add=query(idx)-query(i);
					ans+=add==0?0:add;
					update(idx,-1,220000);
				}
				else{
					visited[i]=true;
					neg[-1*s[i]].poll();
					int idx=pos[-1*s[i]].poll();
					visited[idx]=true;
					long add=query(idx)-query(i);
					ans+=add==0?0:add-1;
					update(idx,-1,220000);

				}
			}
		}
		return ans;
	}
	long[]BIT=new long[250000];
	void update(int x, long val,int n)
	{
		x+=5;
		for(; x <= n; x += x&-x)
			BIT[x] += val;
	}
	long query(int x)
	{
		int cop=x+5;
		long sum = 0;
		for(; cop > 0; cop -= cop&-cop){
			if(cop==150000)
				x=x;
			sum += BIT[cop];

		}
		return sum;
	}
}

Compilation message (stderr)

Note: shoes.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

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