Advertisement
ec1117

Untitled

Jun 29th, 2020
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.16 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 mowing{
  7. public static final String TASKNAME = "mowing";
  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. boolean vert=true;//even is vert
  23. public void solve(int testNumber, InputReader in, PrintWriter out) {
  24. int n=in.nextInt();
  25. int t=in.nextInt();
  26. TreeSet<Triple> sweep=new TreeSet<Triple>();//stores x val and id, negative for removing hor
  27. long count=0;
  28. int arr[][]=new int[n][2];
  29. for(int i=0;i<n;i++) {
  30. arr[i][0]=in.nextInt();
  31. arr[i][1]=in.nextInt();
  32. }
  33. if(arr[0][0]==arr[1][0]) {//first is vert
  34. vert=false;
  35. }
  36. for(int i=1;i<n;i++) {
  37. if((i%2==0)^vert) {//hor
  38. sweep.add(new Triple(arr[i][0],arr[i][1],-i));//- to remove
  39. sweep.add(new Triple(arr[i-1][0],arr[i][1],i));
  40. }
  41. else {
  42.  
  43. sweep.add(new Triple(arr[i][0],arr[i-1][1],i));
  44. }
  45. }
  46. int maxN=(int) Math.pow(10,9)+1;
  47. bit2d bit=new bit2d(maxN,maxN);
  48. while(!sweep.isEmpty()) {
  49. Triple x=sweep.pollFirst();
  50. if(x.z%2==0 ^ vert) {//hor
  51. if(x.z<0) {
  52. // bit.updateBIT(x, -x.z, -1);
  53. }
  54. else {
  55. bit.updateBIT(x.y, x.z, 1);
  56. }
  57. }
  58. else {
  59. int y1=Math.min(arr[x.z][1], arr[x.z-1][1]);
  60. int y2=Math.max(arr[x.z][1], arr[x.z-1][1]);
  61. count+=bit.getRect(y1, 0, y2,x.z-t)+bit.getRect(y1, x.z+t, y2, maxN);
  62. }
  63. }
  64.  
  65. out.println(count);
  66. }
  67.  
  68. }
  69.  
  70. static class bit2d {
  71. int bit[][];
  72. int n;
  73. int m;
  74. bit2d(int n, int m){
  75. bit=new int[n+2][m+2];
  76. this.n=n;
  77. this.m=m;
  78. }
  79. void updateBIT(int x,int y, int val) {
  80. for (; x <= n; x += (x & -x)) {
  81. // updates the 1D bits
  82. for (; y <= m; y += (y & -y))
  83. bit[x][y] += val;
  84. }
  85. return;
  86. }
  87. // sum from (0, 0) to (x, y)
  88. int getSum(int x, int y) {
  89. int sum = 0;
  90. for(; x > 0; x -= x&-x){
  91. for(; y > 0; y -= y&-y){
  92. sum +=bit[x][y];
  93. }
  94. }
  95. return sum;
  96. }
  97. int getRect(int x1, int y1, int x2, int y2) {
  98. int ans = getSum(x2, y2)-getSum(x2, y1 - 1)-getSum(x1 - 1, y2)+getSum(x1 - 1, y1 - 1);
  99. return ans;
  100. }
  101. }
  102.  
  103. static class Pair implements Comparable<Pair>{
  104. int x;
  105. int y;
  106. Pair(int a, int b){
  107. x=a;
  108. y=b;
  109. }
  110. @Override
  111. public int compareTo(Pair arg0) {
  112. if(arg0.x!=x)return x-arg0.x;
  113. return y-arg0.y;
  114. }
  115. }
  116. static class Triple implements Comparable<Triple>{
  117. int x;
  118. int y;
  119. int z;
  120. Triple(int a, int b, int c){
  121. x=a;
  122. y=b;
  123. z=c;
  124. }
  125. @Override
  126. public int compareTo(Triple arg0) {
  127. if(arg0.x!=x)return x-arg0.x;
  128. return y-arg0.y;
  129. }
  130. }
  131.  
  132. static class InputReader {
  133. public BufferedReader reader;
  134. public StringTokenizer tokenizer;
  135.  
  136. public InputReader(InputStream stream) {
  137. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  138. tokenizer = null;
  139. }
  140.  
  141. public String next() {
  142. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  143. try {
  144. tokenizer = new StringTokenizer(reader.readLine());
  145. } catch (IOException e) {
  146. throw new RuntimeException(e);
  147. }
  148. }
  149. return tokenizer.nextToken();
  150. }
  151.  
  152. public int nextInt() {
  153. return Integer.parseInt(next());
  154. }
  155. public long nextLong() {
  156. return Long.parseLong(next());
  157. }
  158. public int[] nextIntArr(int n) {
  159. int arr[]=new int[n];
  160. for(int i=0;i<n;i++) {
  161. arr[i]=this.nextInt();
  162. }
  163. return arr;
  164. }
  165. }
  166. public static class Debug {
  167. private boolean allowDebug;
  168.  
  169. public Debug(boolean allowDebug) {
  170. this.allowDebug = allowDebug;
  171. }
  172.  
  173. private void outputName(String name) {
  174. System.out.print(name + " = ");
  175. }
  176.  
  177. public void debug(String name, int x) {
  178. if (!allowDebug) {
  179. return;
  180. }
  181.  
  182. outputName(name);
  183. System.out.println("" + x);
  184. }
  185.  
  186. public void debug(String name, long x) {
  187. if (!allowDebug) {
  188. return;
  189. }
  190. outputName(name);
  191. System.out.println("" + x);
  192. }
  193.  
  194. public void debug(String name, double x) {
  195. if (!allowDebug) {
  196. return;
  197. }
  198. outputName(name);
  199. System.out.println("" + x);
  200. }
  201.  
  202. public void debug(String name, int[] x) {
  203. if (!allowDebug) {
  204. return;
  205. }
  206. outputName(name);
  207. System.out.println(Arrays.toString(x));
  208. }
  209.  
  210. public void debug(String name, long[] x) {
  211. if (!allowDebug) {
  212. return;
  213. }
  214. outputName(name);
  215. System.out.println(Arrays.toString(x));
  216. }
  217.  
  218. public void debug(String name, double[] x) {
  219. if (!allowDebug) {
  220. return;
  221. }
  222. outputName(name);
  223. System.out.println(Arrays.toString(x));
  224. }
  225.  
  226. public void debug(String name, Object x) {
  227. if (!allowDebug) {
  228. return;
  229. }
  230. outputName(name);
  231. System.out.println("" + x);
  232. }
  233.  
  234. public void debug(String name, Object... x) {
  235. if (!allowDebug) {
  236. return;
  237. }
  238. outputName(name);
  239. System.out.println(Arrays.deepToString(x));
  240. }
  241. }
  242. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement