题目 3232:
蓝桥杯2024年第十五届省赛真题-拼十字
时间限制: 3s
内存限制: 512MB 提交: 215 解决: 17
题目描述
在 LQ 国神秘的古老森林，有一座被称为 “拼十字” 的神秘遗迹。据传，“拼十字” 是由古代文明建造的，它是一个巨大的石头结构，由两个巨大的矩形交叉叠放在一起，形成了一个庄严而神秘的十字形状。这个遗迹被认为是连接人类和神灵之间的通道，拥有神秘的力量和能量。
现在给出 N 个矩形，其中第 i 个矩形的长度和宽度分别问 li，wi，并且矩形颜色 ci 为红 (0)/黄 (1)/蓝 (2) 中的一种。现在小蓝想知道在这 N 个矩形中有多少对矩形可以 “拼十字”？
两个矩形可以“拼十字”的充要条件是：
1. 两个矩形的颜色不同；
2. 矩形 1 的长度严格大于矩形 2 的长度并且矩形 1 的宽度严格小于矩形 2的宽度。
注意，矩形长度和宽度属性是固定的，是不可以通过旋转矩形而发生转变的。
输入格式
第一行一个整数 N，表示有 N 个矩形。接下来 N 行，每行输入三个整数 l、w、c 表示一个矩形的长、宽和颜色。
输出格式
输出一个整数表示答案。由于答案可能会很大，所以你需要将答案对109 + 7 取模之后输出。
样例输入
5 1 10 0 6 6 0 8 6 1 6 10 0 1 2 1
样例输出
2
提示
【样例说明】
第 3 个矩形可以和第 1 个矩形拼十字，第 3 个矩形也可以和第 4 个矩形拼十字。所以一共有两对矩形可以拼十字，答案为 2。
【评测用例规模与约定】对于 30% 的评测用例：1 ≤ N ≤ 5000。对于 100% 的评测用例：1 ≤ N ≤ 105，1 ≤ l,w ≤ 105，0 ≤ c ≤ 2。