[Solution] Points solution codeforces

Points solution codeforces – A triple of points 𝑖i𝑗j and 𝑘k on a coordinate line is called beautiful if 𝑖<𝑗<𝑘i<j<k and 𝑘𝑖𝑑k−i≤d.

Table of Contents

[Solution] Points solution codeforces

You are given a set of points on a coordinate line, initially empty. You have to process queries of three types:

  • add a point;
  • remove a point;
  • calculate the number of beautiful triples consisting of points belonging to the set.
Input

The first line contains two integers 𝑞q and 𝑑d (1𝑞,𝑑21051≤q,d≤2⋅105) — the number of queries and the parameter for defining if a triple is beautiful, respectively.

The second line contains 𝑞q integers 𝑎1,𝑎2,,𝑎𝑞a1,a2,…,aq (1𝑎𝑖21051≤ai≤2⋅105) denoting the queries. The integer 𝑎𝑖ai denotes the 𝑖i-th query in the following way:

  • if the point 𝑎𝑖ai belongs to the set, remove it; otherwise, add it;
  • after adding or removing the point, print the number of beautiful triples.

[Solution] Points solution codeforces

For each query, print one integer — the number of beautiful triples after processing the respective query.

Example
input

Copy
7 5
8 5 3 2 1 5 6
output

Copy
0
0
1
2
5
1
5

 

For Solution

Click Here

Leave a Comment