题目详情题解（0）讨论（0）提交记录（0）

AT_joig2026final_k.お菓子詰め (Packing Snacks)

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

葵は趣味でお菓子作りをしており，作ったお菓子をよく人に配っている． 葵は，JOI 記念日にビ太郎にお菓子をあげる約束をした．

当日，葵は $ N $ 個のお菓子を作った． お菓子には種類と大きさが存在し，種類は $ 1 $ 以上 $ T $ 以下の整数で表される． また，これらのお菓子には $ 1 $ から $ N $ までの番号が付けられている． お菓子 $ i $ ( $ 1 \leqq i \leqq N $ ) の種類は $ A_i $ で，大きさは $ C_i $ である． 葵は $ N $ 個のお菓子のうち，ちょうど $ M $ 個のお菓子を選んでビ太郎の家に持っていく． ここで $ M $ は $ 1 $ 以上 $ N $ 以下の整数である．

ビ太郎は $ M $ 個の袋を持っており，袋には $ 1 $ から $ M $ までの番号が付けられている． 袋 $ j $ ( $ 1 \leqq j \leqq M $ ) には，種類が $ B_j $ でありかつ大きさが $ D_j $ 以下であるお菓子を最大 $ 1 $ 個入れることができる． ビ太郎は，葵が持ってきた $ M $ 個のお菓子のうち，袋に入れることができたお菓子をすべてもらう．

ビ太郎はできるだけ多くのお菓子をもらいたいため，もらえるお菓子の個数がなるべく多くなるように，持ってきたお菓子を袋に入れる． 一方，葵はほかの人にもお菓子を配りたいため，ビ太郎がもらえるお菓子の個数がなるべく少なくなるように，持っていくお菓子を選ぶ． ただし，葵はビ太郎が持っている袋の情報を知っている．

お菓子と袋の情報が与えられたとき，ビ太郎がもらえるお菓子の個数を求めるプログラムを作成せよ．

输入格式

入力は以下の形式で標準入力から与えられる．

$ N $ $ M $ $ T $ $ A_1 $ $ C_1 $ $ A_2 $ $ C_2 $ $ \vdots $ $ A_N $ $ C_N $ $ B_1 $ $ D_1 $ $ B_2 $ $ D_2 $ $ \vdots $ $ B_M $ $ D_M $

输出格式

標準出力に，ビ太郎がもらえるお菓子の個数を $ 1 $ 行で出力せよ．

输入输出样例

  • 输入#1

    5 3 1
1 9
1 3
1 6
1 1
1 5
1 10
1 5
1 5

    输出#1

    2

  • 输入#2

    5 3 3
1 9
2 3
2 6
3 1
3 5
1 10
2 7
2 5

    输出#2

    1

  • 输入#3

    5 5 5
1 9
2 3
3 6
4 1
5 5
1 10
2 7
3 5
4 8
5 6

    输出#3

    4

  • 输入#4

    3 3 2
1 5
1 5
1 1
1 2
1 2
2 2

    输出#4

    1

说明/提示

小課題

  1. ( $ 12 $ 点) $ T = 1 $ ．
  2. ( $ 17 $ 点) $ N \leqq 10 $ ．
  3. ( $ 9 $ 点) $ N = M = T $ ， $ A_i = B_i = i $ ( $ 1 \leqq i \leqq N $ )．
  4. ( $ 36 $ 点) $ N \leqq 5,000 $ ．
  5. ( $ 26 $ 点) 追加の制約はない．

Sample Explanation 1

葵がお菓子 $ 1，3，5 $ を持っていくと，ビ太郎がもらえるお菓子の個数が最も少ない． このとき，ビ太郎は以下のようにお菓子を袋に入れることで，最大 $ 2 $ 個のお菓子をもらうことができる．

  • お菓子 $ 1 $ を袋 $ 1 $ に入れる．
  • お菓子 $ 5 $ を袋 $ 2 $ に入れる．

葵がビ太郎のもらえるお菓子の個数の最大値を $ 2 $ より小さくすることはできないため， $ 2 $ を出力する．

この入力例は小課題 $ 1,2,4,5 $ の制約を満たす．

Sample Explanation 2

葵がお菓子 $ 1，4，5 $ を持っていくと，ビ太郎がもらえるお菓子の個数が最も少ない． このとき，ビ太郎は以下のようにお菓子を袋に入れることで，最大 $ 1 $ 個のお菓子をもらうことができる．

  • お菓子 $ 1 $ を袋 $ 1 $ に入れる．

葵がビ太郎のもらえるお菓子の個数の最大値を $ 1 $ より小さくすることはできないため， $ 1 $ を出力する．

この入力例は小課題 $ 2,4,5 $ の制約を満たす．

Sample Explanation 3

この入力例は小課題 $ 2,3,4,5 $ の制約を満たす．

Sample Explanation 4

この入力例は小課題 $ 2,4,5 $ の制約を満たす．

Constraints

  • $ 1 \leqq N \leqq 500,000 $ ．
  • $ 1 \leqq M \leqq \min(N,5,000) $ ．
  • $ 1 \leqq T \leqq N $ ．
  • $ 1 \leqq A_i \leqq T $ ( $ 1 \leqq i \leqq N $ )．
  • $ 1 \leqq C_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )．
  • $ 1 \leqq B_j \leqq T $ ( $ 1 \leqq j \leqq M $ )．
  • $ 1 \leqq D_j \leqq 10^9 $ ( $ 1 \leqq j \leqq M $ )．
  • 入力される値はすべて整数である．

输入解题思路，AI测评打分。不知道怎么写?

首页