题目内容

某数据采集系统按时间顺序获取了 $n$ 条记录，每条记录包含时间戳 $t_i$、数值 $v_i$ 和质量标记 $q_i$。

其中，质量标记用于表示数据状态：当 $q_i$ 为 $0$ 时表示数据有效，当 $q_i$ 为 $1$ 时表示数据存在可疑情况，当 $q_i$ 为 $2$ 时表示数据无效。系统需要按照无效数据修复、局部异常处理、标准化以及评分计算的顺序依次完成数据处理流程。

阶段一：无效数据修复

对每个满足 $q_i=2$ 的位置 $i$，分别寻找其左侧和右侧最近的满足 $q=0$ 的有效数据下标，记为 $l$ 和 $r$。如果不存在，则对应下标视为未找到。

• 若 $l$ 和 $r$ 均存在，则按时间戳做线性插值： $a_i=v_l+\dfrac{(v_r-v_l)(t_i-t_l)}{t_r-t_l}$。
• 若只存在 $l$，则 $a_i=v_l$。
• 若只存在 $r$，则 $a_i=v_r$。
• 若 $l$ 和 $r$ 均不存在，则 $a_i=v_i$。

其余非无效数据的值保持不变，即 $a_i=v_i$。完成本阶段后得到序列 $a$。

阶段二：局部异常处理

设 $w$ 为奇数，令半径 $h=\frac{w-1}{2}$。对每个位置 $i$，定义窗口下标范围 $[L_i,R_i]$，其中 $L_i=\max(1,i-h)$，$R_i=\min(n,i+h)$。边界处不补值，因此实际窗口大小允许小于 $w$。

对位置 $i$，基于该窗口内第一阶段结果 $a$ 计算：

• 窗口均值 $\mu_i=\frac{1}{R_i-L_i+1}\sum_{j=L_i}^{R_i}a_j$；
• 窗口标准差 $\sigma_i=\sqrt{\frac{1}{R_i-L_i+1}\sum_{j=L_i}^{R_i}(a_j-\mu_i)^2}$。

如果 $|a_i-\mu_i|>k\sigma_i$，则将当前值替换为窗口均值，即 $b_i=\mu_i$；否则保持 $b_i=a_i$。本阶段所有窗口统计量均基于阶段一结束后的序列 $a$，不随本阶段的替换而改变。

阶段三：z-score 标准化

对阶段二得到的序列 $b$ 的全部 $n$ 个值，计算全局均值 $\bar{x}$ 和全局标准差 $s$：

$\bar{x}=\frac{1}{n}\sum_{i=1}^{n}b_i$

$s=\sqrt{\frac{1}{n}\sum_{i=1}^{n}(b_i-\bar{x})^2}$

每个位置的标准化值为 $z_i=\frac{b_i-\bar{x}}{s}$。特别地，如果 $s=0$，则最终分数直接定义为 0。

阶段四：最终评分

根据质量标记定义质量权重 $p_i$：

• 若 $q_i=0$，则 $p_i=1$；
• 若 $q_i=1$，则 $p_i=0.5$；
• 若 $q_i=2$，则 $p_i=0.25$。

取第二阶段结果 $b_i$ 的绝对值，定义原始值权重：

$w_i=\dfrac{p_i|b_i|}{\sum_{j=1}^{n}p_j|b_j|}$

如果分母为 0，则最终分数直接定义为 0。

综合得到特征分数：

$S=\sum_{i=1}^{n}w_i|z_i|$

最终输出将 $S$ 乘以 100 后四舍五入得到的整数。

约束条件

• 记录条数 $n$ 满足 $1\le n\le 10000$。
• 窗口大小 $w$ 满足 $1\le w\le n$，且 $w$ 为奇数。
• 标准差倍数 $k$ 满足 $1\le k\le 10$。
• 数值 $v_i$ 满足 $-10^9\le v_i\le 10^9$。
• 时间戳 $t_i$ 满足 $1\le t_i\le 10^9$，且严格递增。
• 质量标记 $q_i$ 只取 0、1、2 中的一种。
• 至少存在一个 $q_i=0$ 的有效数据记录。

输入描述

第一行包含三个整数 $n$、$w$、$k$，分别表示记录数量、移动窗口大小和异常判断使用的标准差倍数。

接下来包含 $n$ 行，其中第 $i$ 行包含三个整数 $t_i$、$v_i$、$q_i$，依次表示第 $i$ 条记录的时间戳、数值和质量标记。

输出描述

输出一个整数，表示特征分数 $S$ 乘以 100 并四舍五入后的结果。

样例1

输入

1 1 1
1 5 0

输出

0

说明

只有 1 条记录，窗口大小 $w=1$。无效数据修复阶段没有无效记录，因此 $a_1=v_1=5$。

局部异常处理时窗口只包含自身，均值 $\mu_1=5$，标准差 $\sigma_1=0$。由于 $|a_1-\mu_1|=0$，不满足替换条件，所以 $b_1=5$。

第三阶段全局标准差 $s=0$，根据规则最终分数直接定义为 0。

样例2

输入

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

输出

102

说明

第一阶段，第 3 条记录 $q_3=2$。它左侧最近的 $q=0$ 记录是第 1 条，右侧不存在，因此 $a_3=v_1=1$。其余位置保持不变，得到 $a=[1,2,1]$。

第二阶段 $w=1$，每个窗口只包含当前位置，窗口均值等于当前值，标准差为 0，因此所有位置均保持原值，$b=[1,2,1]$。

第三阶段全局均值 $\bar{x}=\frac{4}{3}$，全局标准差 $s=\frac{\sqrt{2}}{3}$。

第四阶段质量权重为 $p_1=1$，$p_2=0.5$，$p_3=0.25$。计算分母 $\sum_{j=1}^{3}p_j|b_j|=2.25$。三个位置的 $|z_i|$ 分别为 $\frac{\sqrt{2}}{2}$、$\sqrt{2}$、$\frac{\sqrt{2}}{2}$。加权求和得到 $S\approx1.0214$，乘以 100 并四舍五入为 102。

样例3

输入

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

输出

141

说明

三条记录均为有效数据，因此无需无效数据修复，$a=[0,0,1]$。

窗口大小 $w=3$，每个位置的窗口都覆盖全部 3 条记录，窗口均值 $\mu=\frac{1}{3}$，标准差 $\sigma=\frac{\sqrt{2}}{3}$。位置 1 和位置 2 的偏差绝对值均为 $\frac{1}{3}$，不大于 $\sigma$，保持原值。位置 3 的偏差绝对值为 $\frac{2}{3}$，大于 $\sigma$，因此 $b_3=\mu=\frac{1}{3}$。得到 $b=[0,0,\frac{1}{3}]$。

第三阶段全局均值 $\bar{x}=\frac{1}{9}$，全局标准差 $s=\frac{\sqrt{2}}{9}$。

第四阶段所有 $q_i=0$，所以 $p_i=1$。分母 $\sum p_j|b_j|=\frac{1}{3}$，只有第 3 条记录的权重非零。其 $|z_3|=\sqrt{2}$，因此 $S=\sqrt{2}$，乘以 100 并四舍五入为 141。