ec1117

Untitled

Jul 5th, 2020
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.88 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3. import java.io.BufferedReader;
  4. import java.awt.Point;
  5.  
  6. public class mincross{
  7. public static final String TASKNAME = "mincross";
  8. public static long mod= 1000000007;
  9. public static Debug db;
  10.  
  11. public static void main(String[] args) throws IOException {
  12. // InputReader in = new InputReader(System.in);
  13. // PrintWriter out = new PrintWriter(System.out);
  14. InputReader in = new InputReader(new FileInputStream(TASKNAME+".in"));
  15. PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(TASKNAME+".out")));
  16. Autocompletion solver = new Autocompletion();
  17. db=new Debug(System.getSecurityManager()==null);
  18. solver.solve(1, in, out);
  19. out.close();
  20. }
  21. static class Autocompletion {
  22.  
  23. public void solve(int testNumber, InputReader in, PrintWriter out) {
  24. int n=in.nextInt();
  25. int l[]=in.nextIntArr(n);
  26. int r[]=in.nextIntArr(n);
  27. int llook[]=new int[n];
  28. int rlook[]=new int[n];
  29. for(int i=0;i<n;i++) {
  30. r[i]--;
  31. l[i]--;
  32. }
  33. for(int i=0;i<n;i++) {
  34. llook[l[i]]=i;
  35. rlook[r[i]]=i;
  36. }
  37. long cnt=0;
  38. bit bit=new bit(n);
  39. for(int i=0;i<n;i++) {
  40. cnt+=i-bit.sum(rlook[l[i]]);
  41. bit.update(rlook[l[i]], 1);
  42. }
  43. long min=Long.MAX_VALUE;
  44. for(int i=n-1;i>=0;i--){
  45. cnt+=llook[r[i]]-(n-1-llook[r[i]]);
  46. min=Math.min(min,cnt);
  47. }
  48. out.println(min);
  49. }
  50. }
  51. static class bit {
  52. //1 indexed
  53. public int[] tree;
  54. public bit(int n) {
  55. tree = new int[n+5];
  56. }
  57. public void update(int index, int val) {
  58. index++;
  59. while(index < tree.length) {
  60. tree[index] += val;
  61. index += index & -index;
  62. }
  63. }
  64. public long sum(int i) {
  65. long ans = 0;
  66. while (i > 0) {
  67. ans += tree[i];
  68. i = i - (i & (-i));
  69. }
  70. return ans;
  71. }
  72.  
  73. public long queryRange(int i, int j) {
  74. return sum(j) - sum(i - 1);
  75. }
  76. }
  77. static class Pair implements Comparable<Pair>{
  78. int x;
  79. int y;
  80. Pair(int a, int b){
  81. x=a;
  82. y=b;
  83. }
  84. @Override
  85. public int compareTo(Pair arg0) {
  86. if(arg0.x!=x)return x-arg0.x;
  87. return y-arg0.y;
  88. }
  89. }
  90. static class Triple implements Comparable<Triple>{
  91. int x;
  92. int y;
  93. int z;
  94. Triple(int a, int b, int c){
  95. x=a;
  96. y=b;
  97. z=c;
  98. }
  99. @Override
  100. public int compareTo(Triple arg0) {
  101. if(arg0.x!=x)return x-arg0.x;
  102. return y-arg0.y;
  103. }
  104. }
  105.  
  106. static class InputReader {
  107. public BufferedReader reader;
  108. public StringTokenizer tokenizer;
  109.  
  110. public InputReader(InputStream stream) {
  111. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  112. tokenizer = null;
  113. }
  114.  
  115. public String next() {
  116. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  117. try {
  118. tokenizer = new StringTokenizer(reader.readLine());
  119. } catch (IOException e) {
  120. throw new RuntimeException(e);
  121. }
  122. }
  123. return tokenizer.nextToken();
  124. }
  125.  
  126. public int nextInt() {
  127. return Integer.parseInt(next());
  128. }
  129. public long nextLong() {
  130. return Long.parseLong(next());
  131. }
  132. public int[] nextIntArr(int n) {
  133. int arr[]=new int[n];
  134. for(int i=0;i<n;i++) {
  135. arr[i]=this.nextInt();
  136. }
  137. return arr;
  138. }
  139. }
  140. public static class Debug {
  141. private boolean allowDebug;
  142.  
  143. public Debug(boolean allowDebug) {
  144. this.allowDebug = allowDebug;
  145. }
  146.  
  147. private void outputName(String name) {
  148. System.out.print(name + " = ");
  149. }
  150.  
  151. public void debug(String name, int x) {
  152. if (!allowDebug) {
  153. return;
  154. }
  155.  
  156. outputName(name);
  157. System.out.println("" + x);
  158. }
  159.  
  160. public void debug(String name, long x) {
  161. if (!allowDebug) {
  162. return;
  163. }
  164. outputName(name);
  165. System.out.println("" + x);
  166. }
  167.  
  168. public void debug(String name, double x) {
  169. if (!allowDebug) {
  170. return;
  171. }
  172. outputName(name);
  173. System.out.println("" + x);
  174. }
  175.  
  176. public void debug(String name, int[] x) {
  177. if (!allowDebug) {
  178. return;
  179. }
  180. outputName(name);
  181. System.out.println(Arrays.toString(x));
  182. }
  183.  
  184. public void debug(String name, long[] x) {
  185. if (!allowDebug) {
  186. return;
  187. }
  188. outputName(name);
  189. System.out.println(Arrays.toString(x));
  190. }
  191.  
  192. public void debug(String name, double[] x) {
  193. if (!allowDebug) {
  194. return;
  195. }
  196. outputName(name);
  197. System.out.println(Arrays.toString(x));
  198. }
  199.  
  200. public void debug(String name, Pair[] x) {
  201. if (!allowDebug) {
  202. return;
  203. }
  204. outputName(name);
  205. StringBuilder sb = new StringBuilder("[");
  206. int cnt=0;
  207. for(Pair y:x) {
  208. sb.append("("+y.x+","+y.y+')');
  209. if (cnt != x.length-1)sb.append(", ");
  210. cnt++;
  211. }
  212. System.out.println(sb.append("]").toString());
  213. }
  214.  
  215. public void debug(String name, Object x) {
  216. if (!allowDebug) {
  217. return;
  218. }
  219. outputName(name);
  220. System.out.println("" + x);
  221. }
  222.  
  223. public void debug(String name, Object... x) {
  224. if (!allowDebug) {
  225. return;
  226. }
  227. outputName(name);
  228. System.out.println(Arrays.deepToString(x));
  229. }
  230. }
  231. }
Advertisement
Add Comment
Please, Sign In to add comment