← 返回题目列表

AtCoder · joisc2020_g

G. 星座3

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

以下是来自日本的原始新闻PDF,已完整保存和染色。

星座 3 (Constellation 3) - 原题 PDF 第 1 页
原题PDF第1页
星座 3 (Constellation 3) - 原题 PDF 第 2 页
原题PDF第2页
星座 3 (Constellation 3) - 原题 PDF 第 3 页
原题PDF第3页
星座 3 (Constellation 3) - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                  Contest Day 3 – Constellation 3

            星座3 (Constellation 3)



  JOI 君は夜景の写真を撮った.この写真は横N ピクセル,縦N ピクセルの画像である.左からx 列目, 下

からy 行目(1 ≦x ≦N, 1 ≦y ≦N) にあるピクセルをピクセル(x, y) と呼ぶ.

 この写真の各ピクセルには,ビル,夜空,星のいずれかが写っており,それぞれの色は白,黒,黄色であ

る.各i (1 ≦i ≦N) について,i 列目にあるピクセルのうち,下からAi 行目まではビルが写っている白いピ
クセルである.星が写っている黄色いピクセルはM 個あり,そのうちj 番目(1 ≦j ≦M) のピクセルはピ
クセル(X j, Yj) である.それ以外のピクセルはすべて夜空の写った黒いピクセルである.
 この写真のある長方形領域が星座を写しているとは,以下の2 つの条件を満たすことを指す.

    • 長方形領域内に白いピクセルがない.

    • 長方形領域内に黄色いピクセルが2 つ以上存在する.

 星座を見るのに飽きたJOI 君は,黄色いピクセルをいくつか黒く塗りつぶすことで,どの長方形領域も星

座を写していないようにしたいと考えた.ただし,黄色いピクセルを塗りつぶすごとに,写真の不自然さが

上がってしまう.具体的には,j 番目(1 ≦j ≦M) の黄色いピクセルを黒く塗ると,写真の不自然さがC j 増
加してしまう.初め,写真の不自然さは0 である.

 写真の情報,及び各黄色のピクセルを塗りつぶすときに増加する不自然さの値が与えられたとき,どの長

方形領域も星座を写していないようにピクセルを塗りつぶしたあとの写真の不自然さの最小値を求めるプロ

グラムを作成せよ.


入力


 入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.


    N

      A1 · · · AN

   M

      X1 Y1 C1
                                 ...

     XM YM CM





                         星座3– 1 / 4

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                  Contest Day 3 – Constellation 3



出力


 どの長方形領域も星座を写していないようにピクセルを塗りつぶしたあとの写真の不自然さの最小値を,

標準出力に1 行で出力せよ.


制約

    • 1 ≦N ≦200 000.
    • 1 ≦Ai ≦N (1 ≦i ≦N).
    • 1 ≦M ≦200 000.
    • 1 ≦X j ≦N (1 ≦j ≦M).
    • 1 ≦Y j ≦N (1 ≦j ≦M).
    • 1 ≦C j ≦1 000 000 000 (1 ≦j ≦M).
    • AXj < Yj (1 ≦j ≦M).
    • (Xj, Yj) , (Xk, Yk) (1 ≦j < k ≦M).


小課題

    1. (14 点) N ≦300,M ≦300.

    2. (21 点) N ≦2 000,M ≦2 000.

    3. (65 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   5                              2

   1 3 4 2 3

   3

   1 5 3

   4 3 2

   2 4 2

 この入力例において,ピクセル(1, 5) を左上の頂点,ピクセル(2, 4) を右下の頂点とする長方形領域が星

座を写している.3 番目の黄色いピクセルを黒く塗ると,写真の不自然さは2 増加し,どの長方形領域も星



                         星座3– 2 / 4

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                  Contest Day 3 – Constellation 3


座を写していないようになる.これが最小値であるので2 を出力する.

 この入力例の写真は図1 の通りである.


                               1

                                    3

                                             2





                         図1


  入力例2              出力例2

   7                              16

   5 6 2 3 6 7 6

   5

   7 7 5

   3 3 7

   3 7 10

   1 7 6

   4 7 8

 この入力例では3 番目,4 番目の黄色いピクセルを黒く塗ればよい.





                         星座3– 3 / 4

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                      Spring Training Camp/Qualifying Trial

                                               March 20–23, 2020 (Komaba, Tokyo)


                                                               Contest Day 3 – Constellation 3


入力例3              出力例3

8                              44

6 8 5 7 3 4 2 1

10

8 2 9

6 6 7

8 3 18

5 8 17

8 5 3

5 5 3

5 4 8

1 8 13

1 7 5

7 4 13





                       星座3– 4 / 4