| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 436821 | bobbilyking | Arranging Shoes (IOI19_shoes) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.*;
import java.util.*;
public class A{
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();
}
long count_swaps(int[] a) {
int n = a.length/2;
Queue<Integer>[] right = new Queue[n+1];
Queue<Integer> allLeft = new ArrayDeque<Integer>();
segtree seg = new segtree(n*2);
for (int i = 0; i <= n; i++) right[i] = new ArrayDeque<Integer>();
for (int i = 0; i <2*n; i++) {
if (a[i] < 0) allLeft.add(i);
else right[a[i]].add(i);
}
long ans = 0 ;
for (int i= 0 ; i < 2*n; i+=2) {
int first = allLeft.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());}
}