Submission #436826

#	Time	Username	Problem	Language	Result	Execution time	Memory
436826		bobbilyking	Arranging Shoes (IOI19_shoes)	Java	45 / 100	547 ms	66936 KiB

shoes

import java.io.*;
import java.util.*;
 
public class shoes{
	public static class segtree {
		long[] t;
		long[] lazy;
		void update(int l, int r, long a) {update(1, 0, t.length/4-1, l, r, a);}
		long query(int l, int r) {return query(1,0,t.length/4-1,l,r);}
		public segtree(int len) {t = new long[len*4];lazy  = new long[len*4];}	
		
		void update(int v, int tl, int tr, int l, int r, long new_val) {
			if (l > r) return;
			if (l == tl && r == tr) {
				t[v] += new_val;
				lazy[v] += new_val;
			}
			else {
				push(v);
				int tm = (tl+tr)/2;
				update(v*2, tl, tm, l, Integer.min(r, tm), new_val);
				update(v*2+1, tm+1,tr, Integer.max(l, tm+1),r, new_val);
				t[v] = t[v*2] + t[v*2+1];
			}
		}
		
		void push(int v) {
			lazy[v*2]+=lazy[v];
			lazy[v*2+1]+=lazy[v];
			t[v*2+1]+=lazy[v];
			t[v*2]+=lazy[v];
			lazy[v]=   0;
		}
		
		long query(int v, int tl, int tr, int l, int r) {
			if (l > r) return 0;
			if (l <= tl && tr <= r) return t[v];
			int tm = (tl+tr)/2;
			push(v);
			return query(v*2, tl, tm, l, Integer.min(r, tm)) + query(v*2+1, tm+1, tr, Integer.max(l, tm+1), r);
		}
	}
 
	
	public static void main(String[] args) throws IOException {
		// br = new BufferedReader(new FileReader(".in"));
		// out = new PrintWriter(new FileWriter(".out"));
		//new Thread(null, new (), "peepee", 1<<28).start();
		//readInput();
	}
	
	
	long count_swaps(int[] a) {
		int n = a.length/2;
		Queue<Integer>[] right = new Queue[n+1];
		Queue<Integer>[] left = new Queue[n+1];
		Queue<Integer> allRight = new ArrayDeque<Integer>();
		segtree seg = new segtree(n*2);
		for (int i = 0; i <= n; i++) {
			right[i] =  new ArrayDeque<Integer>();
			left[i]  =  new ArrayDeque<Integer>();
		}
		for (int i = 0; i <2*n; i++) {
			if (a[i] < 0) left[-a[i]].add(i);
			else {
				right[a[i]].add(i);
				allRight.add(i);
			}
		}
		long ans = 0 ;
		for (int i=  0  ; i  < 2*n; i+=2) {
			int first = left[a[allRight.poll()]].poll();
			long cost = first-i + seg.query(first, first);
			seg.update(0, first, 1);
			int next = right[-a[first]].poll();
			long cost2 = next-(i+1)+seg.query(next, next);
			
			//System.out.println(cost +  " " + cost2);
			
			seg.update(0, next, 1);
			ans+=cost+cost2;
		}
		return ans;
	}
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	static StringTokenizer st = new StringTokenizer("");
	static String read() throws IOException{return st.hasMoreTokens() ? st.nextToken():(st = new StringTokenizer(br.readLine())).nextToken();}
	static int readInt() throws IOException{return Integer.parseInt(read());}
	static long readLong() throws IOException{return Long.parseLong(read());}
	static double readDouble() throws IOException{return Double.parseDouble(read());}
	
}

Compilation message (stderr)

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

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