Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- import java.io.BufferedReader;
- import java.awt.Point;
- public class mowing{
- public static final String TASKNAME = "mowing";
- public static long mod= 1000000007;
- public static Debug db;
- public static void main(String[] args) throws IOException {
- // InputReader in = new InputReader(System.in);
- // PrintWriter out = new PrintWriter(System.out);
- InputReader in = new InputReader(new FileInputStream(TASKNAME+".in"));
- PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(TASKNAME+".out")));
- Autocompletion solver = new Autocompletion();
- db=new Debug(System.getSecurityManager()==null);
- solver.solve(1, in, out);
- out.close();
- }
- static class Autocompletion {
- boolean vert=true;//even is vert
- public void solve(int testNumber, InputReader in, PrintWriter out) {
- int n=in.nextInt();
- int t=in.nextInt();
- TreeSet<Triple> sweep=new TreeSet<Triple>();//stores x val and id, negative for removing hor
- long count=0;
- int arr[][]=new int[n][2];
- for(int i=0;i<n;i++) {
- arr[i][0]=in.nextInt();
- arr[i][1]=in.nextInt();
- }
- if(arr[0][0]==arr[1][0]) {//first is vert
- vert=false;
- }
- for(int i=1;i<n;i++) {
- if((i%2==0)^vert) {//hor
- sweep.add(new Triple(arr[i][0],arr[i][1],-i));//- to remove
- sweep.add(new Triple(arr[i-1][0],arr[i][1],i));
- }
- else {
- sweep.add(new Triple(arr[i][0],arr[i-1][1],i));
- }
- }
- int maxN=(int) Math.pow(10,9)+1;
- bit2d bit=new bit2d(maxN,maxN);
- while(!sweep.isEmpty()) {
- Triple x=sweep.pollFirst();
- if(x.z%2==0 ^ vert) {//hor
- if(x.z<0) {
- // bit.updateBIT(x, -x.z, -1);
- }
- else {
- bit.updateBIT(x.y, x.z, 1);
- }
- }
- else {
- int y1=Math.min(arr[x.z][1], arr[x.z-1][1]);
- int y2=Math.max(arr[x.z][1], arr[x.z-1][1]);
- count+=bit.getRect(y1, 0, y2,x.z-t)+bit.getRect(y1, x.z+t, y2, maxN);
- }
- }
- out.println(count);
- }
- }
- static class bit2d {
- int bit[][];
- int n;
- int m;
- bit2d(int n, int m){
- bit=new int[n+2][m+2];
- this.n=n;
- this.m=m;
- }
- void updateBIT(int x,int y, int val) {
- for (; x <= n; x += (x & -x)) {
- // updates the 1D bits
- for (; y <= m; y += (y & -y))
- bit[x][y] += val;
- }
- return;
- }
- // sum from (0, 0) to (x, y)
- int getSum(int x, int y) {
- int sum = 0;
- for(; x > 0; x -= x&-x){
- for(; y > 0; y -= y&-y){
- sum +=bit[x][y];
- }
- }
- return sum;
- }
- int getRect(int x1, int y1, int x2, int y2) {
- int ans = getSum(x2, y2)-getSum(x2, y1 - 1)-getSum(x1 - 1, y2)+getSum(x1 - 1, y1 - 1);
- return ans;
- }
- }
- static class Pair implements Comparable<Pair>{
- int x;
- int y;
- Pair(int a, int b){
- x=a;
- y=b;
- }
- @Override
- public int compareTo(Pair arg0) {
- if(arg0.x!=x)return x-arg0.x;
- return y-arg0.y;
- }
- }
- static class Triple implements Comparable<Triple>{
- int x;
- int y;
- int z;
- Triple(int a, int b, int c){
- x=a;
- y=b;
- z=c;
- }
- @Override
- public int compareTo(Triple arg0) {
- if(arg0.x!=x)return x-arg0.x;
- return y-arg0.y;
- }
- }
- 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());
- }
- public long nextLong() {
- return Long.parseLong(next());
- }
- public int[] nextIntArr(int n) {
- int arr[]=new int[n];
- for(int i=0;i<n;i++) {
- arr[i]=this.nextInt();
- }
- return arr;
- }
- }
- public static class Debug {
- private boolean allowDebug;
- public Debug(boolean allowDebug) {
- this.allowDebug = allowDebug;
- }
- private void outputName(String name) {
- System.out.print(name + " = ");
- }
- public void debug(String name, int x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, long x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, double x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, int[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, long[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, double[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, Object x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, Object... x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.deepToString(x));
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement