Monday, December 10, 2012

Codeforces Round #153 (Div. 2): C - Points on Line

//  Codeforces Round #153 (Div. 2): C - Points on Line

import java.io.FileInputStream;
import java.io.IOException;
import java.math.*;
import java.util.*;

public class Main2 {
    private static Scanner in;

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        in = new Scanner(System.in);
        if (LOCAL_TEST) {
            in = new Scanner(new FileInputStream("E:\\zin2.txt"));
        }

        Integer N = in.nextInt();
        Long D = in.nextLong();
        Long[] nums = new Long[N];
        for (int i = 0; i < N; i++) {
            nums[i] = in.nextLong();
        }

        long[] plusplus = new long[100001];
        plusplus[0] = 0;
        for (int i = 1; i < plusplus.length; i++) {
            plusplus[i] += plusplus[i - 1] + i;
        }
        Long cnt = 0L;
        for (int i = 0; i < N - 2; i++) {
            int iendMin = i + 2;
            int iendMax = N - 1;
            int iL = iendMin;
            int iR = iendMax;
            int iend = (iL + iR) / 2;
            while (iL < iR) {
                if (nums[iend] - nums[i] > D)
                    iR = iend - 1;
                else
                    iL = iend + 1;
                iend = (iL + iR) / 2;
            }
            if (nums[iend] - nums[i] > D)
                iend--;
            int nn = iend - i - 1;
            // calc 1+2+3+...+nn
            if (nn > 0)
            {
                long add = plusplus[nn];
                cnt += add;
            }
        }
        System.out.println(cnt);

    }

}

No comments:

Post a Comment