Points on Line



 

პატარა გიორგის ძალიან უყვარს წერტილები. ერთხელ მას დედამ აჩუქა OX წრფეზე განლაგებული n ცალი წერტილი. გიორგის აინტერესებს თუ რამდენნაირად შეუძლია მას აირჩიოს 3 განსხვავებული წერტილი ისე, რომ მანძილი ორ ყველაზე დაშორებულს შორის (არჩეული 3-იდან) არ იყოს მეტი d-ზე.

 

შენიშვნა:

წერტილების რიგითობას არჩეულ სამეულში არ აქვს მნიშვნელობა.

 

შესატანი მონაცემები:

პირველი ხაზი: n და d (1 ≤ n ≤ 105; 1 ≤ d ≤ 109).  შემდეგი ხაზი შეიცავს n ცალ მთელ რიცხვს x1, x2, ..., xn. xi < 109.

წერტილის კოორდინატები მკაცრად ზრდადი მიმდევრობით შემოდის.

გამოსატანი მონაცემები:

დაბეჭდეთ ერთი ცალი მთელი რიცხვი, რაოდენობა 3 წერტილიანი სიმრავლეების, რომლებშიც ორ ყველაზე დაშორებულ წერტილებს შორის მანძილი არ არის მეტი d - ზე.

 

შენიშვნა:

ნუ გამოიყენებთ %lld keyword - ს 64 ბიტიანი მთელი რიცხვის წასაკითხად ან დასაბეჭდად. უმჯობესია გამოიყენოთ cin, cout ან %I64d.

 

ტესტი 1:

შესატანი:

4 3

1 2 3 4

გამოსატანი:

4

ტესტი 2:

შესატანი:

4 2

-3 -2 -1 0

გამოსატანი:

2

ტესტი 3:

შესატანი:

5 19

1 10 20 30 50

გამოსატანი:

1


ავირჩიოთ უკიდურესი მარცხენა წერტილი სამეულისა. ამისთვის გადავუყვეთ ყველა წერტილს ზრდადი მიმდევრობით. ამავდროულად გვქონდეს მიმთითებელი უკიდურესი მარცხენა წერტილისთვის, რომელიც დაშორებულია ამჟამინდელ უკიდურეს მარჯვენა წერტილს, ანუ ამჟამინდელ მარჯვენა მიმთითებელს, არაუმეტეს d მანძილისა. თითოეული მარჯვენა წერტილისთვის ვეძებთ დანარჩენ ორ წერტილს. ორეულების რაოდენობა k წერტილიდან არის ჯუფდება k - დან 2 ანუ Ck2 = k * (k - 1) / 2. k = right – left, სადაც right და left შესაბამისად მარჯვენა და მარცხენა უკიდურესი წერტილების მიმთითებლებია(მასივის ინდექსები). დარჩა ის, რომ ავჯამოთ ყველა ასეთი სამეულის რაოდენობა თითოეული მარჯვენა წერტილისთვის.

 

მაგალითი - განხილვა

განვხილიოთ მაგალითი წერტილებისა 1 6 7 8 9 12 სადაც k 3 ის ტოლია.

განვიხილავთ მიმდევრობის წერტილებს და თითოეულ მათგანს ვაფიქსირებთ, როგორც უკიდურეს მარჯვენა წერტილს. პირველი ორი წერტილის, მარჯვენა უკიდურეს წერტილად განხილვას აზრი არ აქვს სამეულს მაინც ვერ შეადგენენ, ვინაიდან მათ მარცხნივ ორი მეზობელი წერტილი არ არის(პირველს საერთოდ არ ჰყავს მარცხენა მეზობელი, ხოლო მეორეს მხოლოდ ერთი). ვიწყებთ right = 2(მესამე ელემენტს) v[right] = 7. ამ დროს left = 0, v[left] = 1, შესრულდება while პირობა და v[left] გახდება 6. დასრულდება while და result გაიზრდება 0 - ით. პასუხი არ შეცვლილა ვინაიდან 7 იანის არჩევა მარჯვენა უკიდურეს წერტილად არ იძლევა სამეულს.

right ინდექსი გახდება 3 ანუ v[right] = 8, left კი ხდება 0. შესრულდება while და v[left] გახდება 6, დასრულდება while და result გაიზრდება 1 ით. სამეულს წარმოადგენენ [6 7 8].

right გახდება 4 ანუ v[right] = 9, while – ის დასრულებისას v[left] იქნება 6 ზე. result გაიზრდება 3 ით. სამეულებია [6 7 9]; [6 8 9]; [7 8 9].

right გახდება 5 ანუ v[right] = 12 (ბოლო იტერაცია!), while - ის შედეგად left გაიზრდება 4 ინდექსამდე ანუ v[left] = 9; result კი გაიზრდება 0 - ით ანუ არ შეიცვლება, რადგანაც სამეული ვერ დგინდება, უკიდურეს მარცხენა და მარჯვენა წერტილებს შორის მხოლოდ ორი წერტილია მოქცეული 9 და 12, რაც სამეულის შესადგენად საკმარისი არ არის.

საბოლოო პასუხი იქნება 4.

 

ამოხსნის კოდი:

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

	int n, d;
	cin >> n >> d;

	int v[1000005];

	for (int i = 0; i < n; i++) {
		int point;
		cin >> point;
		v[i] = point;
	}

	long long result = 0;

	for (int right = 2, left = 0; right < n; right++) {

		while (v[right] - v[left] > d) {
			left++;
		}
		result += (long long)(right - left) * (right - left - 1) / 2;
	}

	cout << result << endl;

	return 0;
}