TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5958
  • Problem
  • P5958楼房重建
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,256m
    Description

    小A的楼房外有一大片施工工地,工地上有N栋待建的楼房。每天,这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆,数自己能够看到多少栋房子。

    为了简化问题,我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置,第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示,其中Hi为第i栋楼房的高度。
    如果这栋楼房上存在一个高度大于0的点与(0,0)的连线没有与之前的线段相交,那么这栋楼房就被认为是可见的。

    施工队的建造总共进行了M天。初始时,所有楼房都还没有开始建造,它们的高度均为0。
    在第i天,建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大—修建,也可以比原来小—拆除,甚至可以保持不变—建筑队这天什么事也没做)。
    请你帮小A数数每天在建筑队完工之后,他能看到多少栋楼房?

    Input Format

    第一行两个正整数N,M
    接下来M行,每行两个正整数Xi,Yi

    Output Format

    M行,第i行一个整数表示第i天过后小A能看到的楼房有多少栋

    Sample Input 1

    3 4
    2 4
    3 6
    1 1000000000
    1 1

    Sample Output 1

    1
    1
    1
    2

    Sample Input 2

    10 100
    6 166267291
    4 764085103
    1 12360641
    1 846991393
    6 383204345
    2 69698641
    9 12331341
    1 772764651
    5 131311041
    10 46049537
    6 690746401
    2 145679903
    10 758217
    4 201987721
    9 249525949
    7 161049529
    6 110578175
    4 231517001
    5 644489651
    7 340648201
    7 151799407
    10 7480386
    3 206257865
    9 328935144
    3 352739143
    7 84581584
    5 29535731
    4 196598419
    6 55312269
    8 11283241
    7 10289281
    4 250134981
    2 208241815
    5 46222012
    6 34664323
    7 359037865
    9 396005251
    2 101892805
    2 210317844
    3 441658977
    5 113743513
    8 44192926
    6 102944206
    4 288727385
    6 233930929
    8 2996745
    2 660629278
    4 32747101
    5 7218281
    9 991959715
    1 130023361
    9 20174977
    10 590823439
    4 609043601
    10 794927517
    8 835448158
    9 79194028
    10 218902057
    3 81328780
    1 842713384
    6 506252986
    9 38734669
    7 134763046
    7 198136601
    6 145100953
    8 139458607
    3 621701089
    10 163368301
    8 162641963
    2 177393360
    8 429881306
    7 165305441
    4 16342951
    10 217025793
    5 32343754
    1 221071391
    4 17866381
    2 1999669
    2 109659346
    10 179614829
    4 59706591
    4 19298137
    8 774219601
    8 6099164
    7 258624081
    5 66188305
    5 64116244
    10 355183187
    2 354022111
    6 3929553
    3 234438274
    5 550657829
    1 283731112
    1 497844261
    7 287715541
    7 434450329
    10 267779521
    5 37026775
    9 7125790
    7 23094767

    Sample Output 2

    1
    1
    2
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    2
    2
    2
    2
    2
    2
    2
    2
    2
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1

    Hint

    对于所有的数据
    \(1<=Xi<=N,1<=Yi<=10^9\)
    \(N,M<=100000\)


    Source  中国国家队清华集训 2012-2013