#PQJ1961x10302. QOJ 1961_10302
QOJ 1961_10302
标题: 天天爱下棋 - Problem - QOJ.ac
The problem was used in the following contests:
小 Z 同学认为下棋非常有趣,于是决定制作一款叫做《天天爱下棋》的游戏。《天天爱下棋》是一个卡牌游戏,需要玩家将背包里的卡牌组合成一个卡组,与其他玩家进行 PK。
这个游戏的每张卡牌共有两个数值——攻击力和防御值,卡牌 A 可以击败卡牌 B 当且仅当卡牌 A 的攻击力大于等于卡牌 B 的防御值。
而这个游戏的卡组恰好由三张两两不同的卡牌组成,顺序放置在三个卡槽中。为了游戏的公平性,三张卡牌能组成一个卡组当且仅当:
- 卡槽1对应的卡牌能击败卡槽2对应的卡牌
- 卡槽2对应的卡牌能击败卡槽3对应的卡牌
- 卡槽3对应的卡牌能击败卡槽1对应的卡牌
开发完成后,小 Z 同学邀请了小 H 同学帮忙测试,并赠予了他 n 张初始卡牌。
现在小 H 想知道,他一共能组出多少种本质不同的卡组,两个卡组不同当且仅当至少存在一个卡槽所对应的卡牌不相同。
输入格式
从标准输入读入数据。
输入第一行包含三个整数 s,n,分别表示子任务编号和卡牌个数。对于样例,s 表示该样例与测试点 s 拥有相同的限制条件。
接下来 n 行,每行包含两个整数 ai,di,分别表示第 i 个卡牌的攻击力和防御值。
输出格式
输出到标准输出。
输出一个整数,表示小 H 一共能组出多少种本质不同的卡组。
样例
输入
1 10
7 4
18 18
10 15
12 3
12 15
9 7
10 1
3 19
11 7
8 13
输出
60
样例二
见下载目录下的 ex_2.in 与 ex_2.ans。
该组样例满足子任务 4 的条件。
样例三
见下载目录下的 ex_3.in 与 ex_3.ans。
该组样例满足子任务 6 的条件。
子任务
对于所有测试数据,保证 1≤n≤2×105, 1≤ai,di≤2×n。
子任务得分n≤特殊性质15500无22,0003105,00042×1045255×1046302×105715有
特殊性质:保证 ∀1≤i≤n,1≤ai,di≤500。