251A - Points on Line - CodeForces Solution

binary search combinatorics two pointers *1300

Please click on ads to support us..

Python Code: 

n, d = map(int, input().split())
a = list(map(int, input().split()))
j = 0
cnt = 0

for i in range(n):
  while a[i] - a[j] > d:
    j += 1
  k = i - j
  cnt += k * (k -1) // 2

print(cnt)

C++ Code: 

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
   long x, y;
   cin >> x >> y;
   vector<long long> v;
   while (x--) {
      long temp;
      cin >> temp;
      v.push_back(temp);
   }
 
   long long out = 0;
   for (long i = 0; i < v.size(); i++) {
      long long comp = v[i] + y;
      long long l = i, r = v.size() - 1;
      long long ans = 0;
      while (l <= r) {
         long long mid = l + (r - l) / 2;
         if (v[mid] == comp) {
            ans = mid;
            break;
         }
         else if (v[mid] < comp) {
            ans = mid;
            l = mid + 1;
         }
         else {
            r = mid - 1;
         }
      }
      if (ans - i < 2)continue;
      long long numb = ans - i;
      if (numb == 2) {
         out++;
      }
      else {
         out = out + (numb*(numb-1)/2l);
      }
   }
   cout << out;
}


Comments

Submit
0 Comments
More Questions

1028B - Unnatural Conditions
735B - Urbanization
746C - Tram
1278B - A and B
1353D - Constructing the Array
1269C - Long Beautiful Integer
1076A - Minimizing the String
913C - Party Lemonade
1313A - Fast Food Restaurant
681A - A Good Contest
1585F - Non-equal Neighbours
747A - Display Size
285A - Slightly Decreasing Permutations
515C - Drazil and Factorial
1151E - Number of Components
1151F - Sonya and Informatics
556A - Case of the Zeros and Ones
867A - Between the Offices
1569A - Balanced Substring
260A - Adding Digits
1698C - 3SUM Closure
1029B - Creating the Contest
1421A - XORwice
1029A - Many Equal Substrings
1675D - Vertical Paths
1271C - Shawarma Tent
805A - Fake NP
1163A - Eating Soup
787A - The Monster
807A - Is it rated