TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4526
  • 题目
  • P4526[CERC2015]奶牛围栏
    限制 : 时间限制 : 25000 MS   空间限制 : 565536 KB
    评测说明 : 2.5s,512m
    问题描述

    一个10^6行10^6列的网格图,上面有一些牛、花和一些矩形围栏,围栏在格子的边界上,牛和花在格子里,牛只能向下或向右走,牛也不能穿过围栏和地图边界,求每头牛它能到达的花的数量。注意栅栏不会相交

    输入格式

    第一行一个数f表示矩形围栏的数量。

    接下来f行,每行四个数x1,y1,x2,y2,表示(x1,y1)在围栏内部矩形的左上角,(x2,y2)在右下角。

    接下来一行一个数m表示花的数量。

    接下来m行每行两个数x,y,表示在(x,y)处有一朵花。

    接下来一行一个数n表示牛的数量。

    接下来n行每行两个数x,y,表示在(x,y)处有一头牛。

    输出格式

    总共n行,每行一个数ans,第i个数表示第i头牛能到ans个花。

    样例输入 1

    4
    2 2 8 4
    1 9 4 10
    6 7 9 9
    3 3 7 3
    9
    3 4
    8 4
    11 5
    10 7
    10 8
    9 8
    2 8
    4 11
    9 11
    8
    1 1
    5 10
    6 9
    3 7
    7 1
    4 2
    7 5
    3 3

    样例输出 1

    5
    1
    0
    1
    3
    1
    3
    0

    样例输入 2

    10
    92 41 99 47
    84 98 85 98
    91 26 98 29
    36 23 40 27
    66 84 70 93
    5 32 14 39
    38 92 44 96
    68 2 75 7
    76 33 83 38
    60 54 67 56
    10
    85 21
    66 78
    30 80
    81 24
    60 70
    17 95
    73 63
    98 97
    53 85
    52 47
    10
    91 96
    61 31
    77 24
    50 48
    5 5
    15 37
    93 77
    14 41
    20 32
    2 87

    样例输出 2

    1
    2
    2
    5
    10
    8
    1
    8
    7
    2

    提示

    0<=f<=200000

    0<=m<=200000

    1<=n<=200000