#P17797. [Ontak2024]NAJ

[Ontak2024]NAJ

题目描述

给定 nn 个点,第 ii 个点的坐标为 (ai,bi)(a_i,b_i),颜色为 cic_i。共有 kk 种颜色,每种颜色至少出现一次。

定义两个点的差异值为

$$f(i,j)=\begin{cases} (a_i-a_j)^2+(b_i-b_j)^2,&c_i\ne c_j,\\ 0,&c_i=c_j. \end{cases}$$

求最大的差异值。所有点颜色相同时,答案为 00。

输入格式

第一行两个整数 n,kn,k。随后 nn 行,每行三个整数 ai,bi,cia_i,b_i,c_i。

输出格式

输出一个整数,表示最大差异值。

数据范围

  • 1≤k≤n≤250 0001\le k\le n\le250\,000。
  • 0≤ai,bi≤1090\le a_i,b_i\le10^9,1≤ci≤k1\le c_i\le k。
  • 每种颜色至少出现一次。题面未保证不同点的坐标互异。

样例

输入:

4 3
0 2 1
1 3 3
3 4 1
2 2 2

输出:

5

第 2、3 个点颜色不同,距离平方为 (1−3)2+(3−4)2=5(1-3)^2+(3-4)^2=5,达到最大值。

官方附加样例说明

  • 0b:n=k=2n=k=2,(a1,b1)=(0,0)(a_1,b_1)=(0,0),(a2,b2)=(109,109)(a_2,b_2)=(10^9,10^9),ci=ic_i=i。答案 2×10182\times10^{18}。
  • 0c:n=5000,k=1n=5000,k=1,ai=bi=i2+7,ci=1a_i=b_i=i^2+7,c_i=1。答案 00。
  • 0d:n=250000,k=2n=250000,k=2,ai=bi=2i,ci=(i mod 2)+1a_i=b_i=2i,c_i=(i\bmod2)+1。答案 499996000008499996000008。

子任务

编号 附加限制 分值
1 n≤5000n\le5000 3
2 所有 bi=0b_i=0 8
3 k=nk=n 30
4 k=2k=2 38
5 无附加限制 21