-
Notifications
You must be signed in to change notification settings - Fork 0
/
circlecross.java
63 lines (55 loc) · 1.41 KB
/
circlecross.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// Why Did the Cow Cross the Road III
import java.util.*;
import java.io.*;
public class circlecross {
static int[] BIT;
public static void main(String[] args) throws IOException {
String file = "circlecross";
BufferedReader br = new BufferedReader(new FileReader(new File(file + ".in")));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int[][] pts = new int[N][2];
int[] circle = new int[N*2];
for(int[] a: pts) Arrays.fill(a, -1);
for(int i = 0; i < N*2; i++) {
st = new StringTokenizer(br.readLine());
int id = Integer.parseInt(st.nextToken()) - 1;
circle[i] = id;
if(pts[id][0] == -1) pts[id][0] = i;
else pts[id][1] = i;
}
br.close();
int result = 0;
BIT = new int[N*2 + 1];
for(int pt = 0; pt < N*2; pt++) {
int start = pts[circle[pt]][0];
if(start == pt) { // start
add(start, true);
} else { // end
add(start, false);
result += sum(pt-1) - sum(start);
}
}
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(new File(file + ".out"))));
System.out.println(result);
out.println(result);
out.close();
}
public static int sum(int m) {
m++;
int sum = 0;
while (m > 0) {
sum += BIT[m];
m -= m & (-m);
}
return sum;
}
public static void add(int m, boolean add) {
m++;
while (m <= BIT.length) {
if(add) BIT[m]++;
else BIT[m]--;
m += m & (-m);
}
}
}