← 返回题目列表

AtCoder · tkppc2016_i

I. 老板

中文机器翻译题面 查看原题

問題文

Joisino Onee-chan的下一个任务是调整boss战的难度。
这个 Boss 的身体上有像网格一样排列的单元,从左上角的单元开始到右侧。x,如下y高级位置的单元格是 由(x,y)代表。
在与这个boss的战斗中,N事件发生。活动如下3是其中一种类型

  • 事件1
  • 一些整数 关于L,R。这是K第次活动1如果是这样,y坐标是K-1在,x坐标是L减去R之间的细胞被削弱。 给出
  • 事件2
  • 一些整数 关于K,y座標K细胞的弱化被移除。这个时候一定要y座標K肯定有削弱的细胞。
  • 事件3
  • 一些整数 关于L,R你有一次机会攻击boss。
  • 某些部分被削弱。y座標K和被削弱的细胞有 如果达到x座標A减去B, 只有在A<L和R<B时才能攻击该部分。
  • 当你攻击时, 你可以对 Boss 造成(L-A)×(B-R)点伤害。
  • 所有赛事难度调整 在3中,我想提前知道可以对boss造成的最大伤害。
    Joisino 的工作就是所有事件 在3中,目的是创建一个程序来计算可以对 Boss 造成的最大伤害。


    入力

    输入是按以下格式从标准输入给出的。

    N
    :
    
    • 1行包含一个整数,表示将发生的事件数。 写入有关发生的第N(1 ≦ N ≦ 2×10^5)。 表示
    • 继续N行i行中,i个事件的信息。
    • 每行的开头是一个表示事件类型的整数。T_i(1≦T_i≦3)。 表示
    • T_i是 在1后跟一个整数 给出了L_i(0≦L_i≦10^9),R_i(L_i≦R_i≦10^9)并且这个K第次活动1如果是这样,y坐标是K-1在,x坐标是L_i减去R_i这意味着中间的细胞被削弱了。
    • T_i是 在2后跟一个整数 给出了K_i,y座標K_i表示削弱的细胞被去除。 给出
    • T_i是 在3后跟一个整数 给出了L_i(0≦L_i≦10^9),R_i(L_i≦R_i≦10^9),意味着你有一次攻击Boss的机会。

    配点

    针对此问题设置了部分分数。

  • 数据集1是 可以表示为N(1≦N≦3×10^3)并且回答正确,5点。
  • 数据集2没有额外的限制,如果你回答正确,155点。
  • 出力

    所有事件 对于3,计算可以对 Boss 造成的最大伤害。1行输出。
    如果有y如果你连坐标都无法攻击, 输出-1。


    入力例1

    9
    1 0 10
    1 2 12
    3 5 5
    3 8 9
    2 0
    3 5 5
    3 8 9
    2 1
    3 5 5
    

    出力例1

    25
    18
    21
    18
    -1
    

  • 第一2事件削弱后,boss的状态如下图所示(被削弱的部分以红色显示)。
  • 在下一个事件攻击机会中, 当你攻击y座標0时, 造成(5-0)×(10-5)=25伤害。
  • 在下一个事件攻击机会中, 当你攻击y座標1时, 造成(8-2)×(12-9)=18伤害。
  • 下一个事件的削弱被移除后,boss的状态将如下图所示。
  • 在下一个事件攻击机会中, 当你攻击y座標1时, 造成(5-2)×(12-5)=21伤害。
  • 在下一个事件攻击机会中, 当你攻击y座標1时, 造成(8-2)×(12-9)=18伤害。
  • 下一个事件的削弱被移除后,boss的状态将如下图所示。
  • 在下一个事件的攻击几率中,你可以攻击。y由于没有坐标, 输出-1。 我锻炼

  • 入力例2

    7
    1 3 7
    1 0 6
    1 4 10
    3 1 3
    3 6 7
    3 5 5
    3 4 6
    

    出力例2

    3
    6
    5
    1
    

    入力例3

    20
    3 268323303 605806817
    3 397106901 526645597
    1 242167025 963419065
    3 306157656 666722488
    3 90905255 723611215
    1 135062270 656996756
    1 72048580 708895403
    1 254360876 741288738
    3 353173849 652094091
    3 274378199 520888695
    1 128877839 722596185
    3 367349293 905356554
    3 336742409 649201453
    1 353239854 521572577
    2 3
    3 5185803 799351855
    1 139746807 783110900
    3 375190636 656724546
    1 462675641 992773167
    1 77055484 555060299
    

    出力例3

    -1
    -1
    18985801177770087
    -1
    34559196595622576
    38039325599084252
    7268396812754948
    29717251314463008
    -1
    40797612391288109