P2154 [SDOI2009]虔诚的墓主人

    • 183通过
    • 395提交
  • 题目提供者 xmyzwls 管理员
  • 评测方式 云端评测
  • 标签 排列组合 数论,数学 树状数组 各省省选 2009 山东 高性能
  • 难度 省选/NOI-
  • 时空限制 800ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小W是一片新造公墓的管理人。公墓可以看成一块N×M的矩形,矩形的每个格点,要么种着一棵常青树,要么是一块还没有归属的墓地。

    当地的居民都是非常虔诚的基督徒,他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚,他们希望自己的墓地拥有着较高的虔诚度。

    一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地,墓地的正上、正下、正左、正右都有恰好k棵常青树。

    小W希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少。

    输入输出格式

    输入格式:

    输入文件religious.in的第一行包含两个用空格分隔的正整数N和M,表示公墓的宽和长,因此这个矩形公墓共有(N+1) ×(M+1)个格点,左下角的坐标为(0, 0),右上角的坐标为(N, M)。

    第二行包含一个正整数W,表示公墓中常青树的个数。

    第三行起共W行,每行包含两个用空格分隔的非负整数xi和yi,表示一棵常青树的坐标。输入保证没有两棵常青树拥有相同的坐标。

    最后一行包含一个正整数k,意义如题目所示。

    输出格式:

    输出文件religious.out仅包含一个非负整数,表示这片公墓中所有墓地的虔诚度总和。为了方便起见,答案对2,147,483,648取模。

    输入输出样例

    输入样例#1: 复制
    5 6
    13
    0 2
    0 3
    1 2
    1 3
    2 0
    2 1
    2 4
    2 5
    2 6
    3 2
    3 3
    4 3
    5 2
    2
    输出样例#1: 复制
    6

    说明

    图中,以墓地(2, 2)和(2, 3)为中心的十字架各有3个,即它们的虔诚度均为3。其他墓

    地的虔诚度为0。

    对于30%的数据,满足1 ≤ N, M ≤ 1,000。

    对于60%的数据,满足1 ≤ N, M ≤ 1,000,000。

    对于100%的数据,满足1 ≤ N, M ≤ 1,000,000,000,0 ≤ xi ≤ N,0 ≤ yi ≤ M,1 ≤ W ≤ 100,000,1 ≤ k ≤ 10。

    存在50%的数据,满足1 ≤ k ≤ 2。

    存在25%的数据,满足1 ≤ W ≤ 10000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。