TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4616
  • 题目
  • P4616【USACO 2018 JAN Platinum】喷洒器
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    评测说明 : 1s,256m
    问题描述

     农夫约翰有一块很大的田,他正在考虑种甜玉米。经过对他农田的调查,FJ发现它形成了一个(N-1)×(N-1)的

    正方形。西南角为坐标(0,0),东北角是(N-1,N-1)。在某些整数坐标的位置中有双头喷头,每一个都能够同

    时喷洒水和肥料。一个在(i,j)处的双头喷头会将水洒在农田中所有在其东面且在其北面的区域,将肥料洒在农

    田中所有在其南面且在其西面的区域。形式化地说,这个喷头将会将水洒在所有满足N≥x≥i和N≥y≥j的实数坐标

    (x,y)上,会将肥料洒在所有满足0≤x≤i和0≤y≤j的实数坐标上农民约翰想在一些边与坐标轴平行的长方形农田

    里种植甜玉米。然而,为了甜玉米的生长,矩形内的所有点都必须由双头喷头浇水和施肥。当然,矩形必须有正的

    面积,否则农民约翰就不能在里面种植任何玉米!帮助农民约翰确定可以种植甜玉米的拥有正面积的矩形农田数。

    由于这个数字可能很大,所以输出对为10^9 + 7取模

    输入格式

     第一行包含一个整数N,表示农场的大小(1≤N≤10^5)。

    接下来的n行各包含两个由空格分隔的整数。这些整数中0≤i,j≤N-1,这表示有一个双头喷头位于(i,j)的位置。

    保证每列都有一台喷头,每排正好有一台喷头。这也就是说,没有两个喷头有相同的x坐标或y坐标。

    输出格式

    输出包含一行,表示方案数,对 10^9+7 取模。

    样例输入

    5
    0 4
    1 1
    2 2
    3 0
    4 3

    样例输出

    21

    提示

    对于100%的数据:1≤N≤10^5,0≤i,j≤N−1。