| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 172262 | ijxjdjd | 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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.PriorityQueue;
import java.util.AbstractQueue;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.ArrayDeque;
import java.util.Comparator;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class shoes {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
shoe solver = new shoe();
solver.solve(1, in, out);
out.close();
}
static class shoe {
public void solve(int testNumber, InputReader in, PrintWriter out) {
int N = in.nextInt();
ArrayDeque<Integer>[] left = new ArrayDeque[N];
ArrayDeque<Integer>[] right = new ArrayDeque[N];
for (int i = 0; i < N; i++) {
left[i] = new ArrayDeque<>();
right[i] = new ArrayDeque<>();
}
FenwickTree unset = new FenwickTree(2 * N);
for (int i = 0; i < 2 * N; i++) {
int a = in.nextInt();
if (a < 0) {
left[(-a) - 1].add(i);
} else {
right[a - 1].add(i);
}
unset.add(i, 1);
}
long res = 0;
PriorityQueue<int[]> next = new PriorityQueue<>(new Comparator<int[]>() {
public int compare(int[] ints, int[] t1) {
return Integer.compare(ints[0] + ints[1] + (ints[0] > ints[1] ? 1 : 0), t1[0] + t1[1] + (t1[0] > t1[1] ? 1 : 0));
}
});
for (int i = 0; i < N; i++) {
if (left[i].size() > 0) {
next.add(new int[]{left[i].remove(), right[i].remove(), i});
}
}
for (int i = 0; i < N; i++) {
int[] a = next.remove();
res += (unset.sum(a[0]) - 1);
unset.add(a[0], -1);
res += (unset.sum(a[1]) - 1);
unset.add(a[1], -1);
if (left[a[2]].size() > 0) {
next.add(new int[]{left[a[2]].remove(), right[a[2]].remove(), a[2]});
}
}
out.println(res);
}
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
static class FenwickTree {
public int[] BIT;
public int size = 0;
public FenwickTree(int N) {
BIT = new int[N];
size = N;
}
public FenwickTree(int[] arr) {
size = arr.length;
BIT = new int[arr.length];
for (int i = 0; i < size; i++) {
add(i, arr[i]);
}
}
public void add(int id, int add) {
for (int i = id; i < size; i |= i + 1) {
BIT[i] += add;
}
}
public int sum(int r) {
if (r < 0 || r >= size) {
return 0;
}
int res = 0;
for (int i = r; i >= 0; i = ((i) & (i + 1)) - 1) {
res += BIT[i];
}
return res;
}
}
}