#PQJ1961x10302. QOJ 1961_10302

    ID: 2762 传统题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTT 2023背包枚举

QOJ 1961_10302

标题: 天天爱下棋 - Problem - QOJ.ac

Statistics

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。