← 返回题目列表

AtCoder · joisc2016_d

D. 就业规划

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

以下是来自日本的官方日本新闻原版PDF,已完整保存并按原样染色。

雇用計画 - 原题 PDF 第 1 页
原题PDF第1页
雇用計画 - 原题 PDF 第 2 页
原题PDF第2页
雇用計画 - 原题 PDF 第 3 页
原题PDF第3页
雇用計画 - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                      Contest Day 2 – Employment


                   雇用計画(Employment)



 あなたはJust Odd Inventions 社を知っているだろうか?この会社の業務は「ただ奇妙な発明(just odd
inventions)」をすることである.ここでは略してJOI 社と呼ぶ.
  JOI 社は事業を拡大するため,新たに社員を雇用することになった.
 社員の候補者がN 人いる.候補者にはそれぞれ1 からN までの番号が付けられており,それぞれの候補
者には評価値と呼ばれる一つの整数が定められている.
 今回の雇用では,評価値がある値以上の候補者を全員採用する.新たに採用された社員をいくつかのグ
ループに分ける.新たに採用された社員のグループを,次の条件をみたすように作る.

   • 候補者a と候補者b (a < b) が両方とも採用されたとき,これらの社員が同じグループに入るのは,候
   補者c (a ≦c ≦b) が全員採用された場合であり,かつそのときに限る.

  JOI 社の人事担当であるあなたは,クエリを合計M 個順に処理することで,今回の雇用において作られ
るグループの個数を見積もることになった.j 番目のクエリは,以下の2 種類のうちのいずれかである.

   • 評価値がBj 以上の候補者を全員採用する場合に作られるグループの個数を求める.この種類のクエ
   リを解答クエリと呼ぶ.

   • 候補者C j の評価値をDj に更新する.この種類のクエリを更新クエリと呼ぶ.


課題

 M 個のクエリについての情報が与えられたとき,それぞれの解答クエリに対するグループの個数を求め
るプログラムを作成せよ.


入力

 標準入力から以下のデータを読み込め.

   • 1 行目には,整数N, M が空白を区切りとして書かれている.これは,社員の候補者がN 人いて,あ
  なたがM 個のクエリを処理することを表す.

   • 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数Ai が書かれている.これは,クエリを処理する以
   前は,候補者i の評価値がAi であることを表す.

   • 続くM 行のうちのj 行目(1 ≦j ≦M) には,2 個または3 個の整数が空白を区切りとして書かれて
   いる.1 個目の整数をT j とすると,この行の内容は以下のいずれかである.

         1. T j = 1 のとき.この行には整数T j, Bj が空白を区切りとして書かれている.これは,j 番目のク
     エリが,評価値がBj 以上の候補者を全員採用する場合に作られるグループの個数を求める解答
     クエリであることを表す.



                      雇用計画– 1 / 4

Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                      Contest Day 2 – Employment


         2. T j = 2 のとき.この行には整数T j,C j, Dj が空白を区切りとして書かれている.これは,j 番目
     のクエリが,候補者C j の評価値をD j に更新する更新クエリであることを表す.


出力

 標準出力に,それぞれの解答クエリに対するグループの個数を順に1 行ずつ出力せよ,


制限

 すべての入力データは以下の条件を満たす.

   • 1 ≦N ≦200 000.

   • 1 ≦M ≦200 000.

   • 1 ≦Ai ≦1 000 000 000 (1 ≦i ≦N).

   • 1 ≦T j ≦2 (1 ≦j ≦M).

   • 1 ≦Bj ≦1 000 000 000 (1 ≦j ≦M).

   • 1 ≦C j ≦N (1 ≦j ≦M).

   • 1 ≦Dj ≦1 000 000 000 (1 ≦j ≦M).

   • T j = 1 となるj (1 ≦j ≦M) は少なくとも一つ存在する.


小課題

小課題1 [10 点]

 以下の条件を満たす.

   • N ≦2 000.

   • M ≦2 000.


小課題2 [30 点]

   • T j = 1 (1 ≦j ≦M) を満たす.


小課題3 [60 点]

 追加の制限はない.



                      雇用計画– 2 / 4

Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                      Contest Day 2 – Employment


入出力例

  入力例1        出力例1
   5 4                  2
   8                    1
   6                    2
   3
   5
   4
   1 5
   2 4 1
   1 5
   1 3


   1. 1 番目のクエリは解答クエリである.評価値が5 以上である候補者1, 候補者2, 候補者4 を採用した
   場合,候補者1 と候補者2 からなるグループと,候補者4 からなるグループの2 個のグループが作ら
   れるので,2 を出力する.

   2. 2 番目のクエリは更新クエリである.候補者4 の評価値を1 に更新する.

   3. 3 番目のクエリは解答クエリである.評価値が5 以上である候補者1 と候補者2 を採用した場合,候
   補者1 と候補者2 からなる1 個のグループが作られるので,1 を出力する.

   4. 4 番目のクエリは解答クエリである.評価値が3 以上である候補者1, 候補者2, 候補者3, 候補者5 を
   採用した場合,候補者1, 候補者2, 候補者3 からなるグループと,候補者5 からなるグループの2 個
   のグループが作られるので,2 を出力する.





                      雇用計画– 3 / 4

Japanese Olympiad in Informatics 2015/2016
                                                         Spring Training Camp/Qualifying Trial
                                             March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                    Contest Day 2 – Employment



 入力例2        出力例2
 7 5                  0
 13                   1
 19                   3
 1                    3
 15                   2
 13
 1
 19
 1 20
 1 1
 1 6
 1 11
 1 17

入力例2 は小課題2 の制限を満たす.



 入力例3        出力例3
 10 5                 2
 8                    1
 10                   0
 15
 2
 2
 8
 5
 12
 11
 4
 1 5
 2 8 4
 1 12
 2 5 11
 1 16





                     雇用計画– 4 / 4