B. Interesting drink

Codeforces

IDCF706B

Time2000ms

Memory256MB

Difficulty—

binary searchdpimplementation

English · Original

Chinese · Translation

Formal · Original

Vasiliy likes to rest after a hard work, so you may often meet him in some bar nearby. As all programmers do, he loves the famous drink "_Beecola_", which can be bought in _n_ different shops in the city. It's known that the price of one bottle in the shop _i_ is equal to _x__i_ coins. Vasiliy plans to buy his favorite drink for _q_ consecutive days. He knows, that on the _i_\-th day he will be able to spent _m__i_ coins. Now, for each of the days he want to know in how many different shops he can buy a bottle of "_Beecola_". ## Input The first line of the input contains a single integer _n_ (1 ≤ _n_ ≤ 100 000) — the number of shops in the city that sell Vasiliy's favourite drink. The second line contains _n_ integers _x__i_ (1 ≤ _x__i_ ≤ 100 000) — prices of the bottles of the drink in the _i_\-th shop. The third line contains a single integer _q_ (1 ≤ _q_ ≤ 100 000) — the number of days Vasiliy plans to buy the drink. Then follow _q_ lines each containing one integer _m__i_ (1 ≤ _m__i_ ≤ 109) — the number of coins Vasiliy can spent on the _i_\-th day. ## Output Print _q_ integers. The _i_\-th of them should be equal to the number of shops where Vasiliy will be able to buy a bottle of the drink on the _i_\-th day. [samples] ## Note On the first day, Vasiliy won't be able to buy a drink in any of the shops. On the second day, Vasiliy can buy a drink in the shops 1, 2, 3 and 4. On the third day, Vasiliy can buy a drink only in the shop number 1. Finally, on the last day Vasiliy can buy a drink in any shop.

Vasiliy 喜欢在辛苦工作后休息，因此你经常能在附近的酒吧遇到他。和所有程序员一样，他热爱一种名为 "_Beecola_" 的饮料，这种饮料在城市中有 #cf_span[n] 家商店出售。已知第 #cf_span[i] 家商店中一瓶饮料的价格为 #cf_span[xi] 枚硬币。 Vasiliy 计划连续 #cf_span[q] 天购买他最爱的饮料。他知道，在第 #cf_span[i] 天，他最多能花费 #cf_span[mi] 枚硬币。现在，对于每一天，他想知道有多少家不同的商店可以购买到一瓶 "_Beecola_"。输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 城市中出售 Vasiliy 最爱饮料的商店数量。第二行包含 #cf_span[n] 个整数 #cf_span[xi] (#cf_span[1 ≤ xi ≤ 100 000]) —— 第 #cf_span[i] 家商店中饮料瓶的价格。第三行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100 000]) —— Vasiliy 计划购买饮料的天数。接下来的 #cf_span[q] 行，每行包含一个整数 #cf_span[mi] (#cf_span[1 ≤ mi ≤ 10^9]) —— Vasiliy 在第 #cf_span[i] 天能够花费的硬币数量。请输出 #cf_span[q] 个整数。第 #cf_span[i] 个整数应等于 Vasiliy 在第 #cf_span[i] 天能够购买到一瓶饮料的商店数量。在第一天，Vasiliy 无法在任何一家商店购买饮料。在第二天，Vasiliy 可以在第 #cf_span[1]、#cf_span[2]、#cf_span[3] 和 #cf_span[4] 家商店购买饮料。在第三天，Vasiliy 只能在第 #cf_span[1] 家商店购买饮料。最后，在最后一天，Vasiliy 可以在任何一家商店购买饮料。 ## Input 输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 城市中出售 Vasiliy 最爱饮料的商店数量。第二行包含 #cf_span[n] 个整数 #cf_span[xi] (#cf_span[1 ≤ xi ≤ 100 000]) —— 第 #cf_span[i] 家商店中饮料瓶的价格。第三行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100 000]) —— Vasiliy 计划购买饮料的天数。接下来的 #cf_span[q] 行，每行包含一个整数 #cf_span[mi] (#cf_span[1 ≤ mi ≤ 10^9]) —— Vasiliy 在第 #cf_span[i] 天能够花费的硬币数量。 ## Output 请输出 #cf_span[q] 个整数。第 #cf_span[i] 个整数应等于 Vasiliy 在第 #cf_span[i] 天能够购买到一瓶饮料的商店数量。 [samples] ## Note 在第一天，Vasiliy 无法在任何一家商店购买饮料。在第二天，Vasiliy 可以在第 #cf_span[1]、#cf_span[2]、#cf_span[3] 和 #cf_span[4] 家商店购买饮料。在第三天，Vasiliy 只能在第 #cf_span[1] 家商店购买饮料。最后，在最后一天，Vasiliy 可以在任何一家商店购买饮料。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of shops. Let $ X = (x_1, x_2, \dots, x_n) $ be a sequence of positive integers representing the price of one bottle in each shop. Let $ q \in \mathbb{Z}^+ $ be the number of days. Let $ M = (m_1, m_2, \dots, m_q) $ be a sequence of positive integers where $ m_i $ is the number of coins Vasiliy can spend on day $ i $. **Constraints** 1. $ 1 \leq n \leq 100{,}000 $ 2. $ 1 \leq x_i \leq 100{,}000 $ for all $ i \in \{1, \dots, n\} $ 3. $ 1 \leq q \leq 100{,}000 $ 4. $ 1 \leq m_i \leq 10^9 $ for all $ i \in \{1, \dots, q\} $ **Objective** For each day $ i \in \{1, \dots, q\} $, compute: $$ f(m_i) = \left| \left\{ j \in \{1, \dots, n\} \mid x_j \leq m_i \right\} \right| $$ That is, the number of shops where the price is at most $ m_i $.

Samples

Input #1

5
3 10 8 6 11
4
1
10
3
11

Output #1

API Response (JSON)

{
  "problem": {
    "name": "B. Interesting drink",
    "description": {
      "content": "Vasiliy likes to rest after a hard work, so you may often meet him in some bar nearby. As all programmers do, he loves the famous drink \"_Beecola_\", which can be bought in _n_ different shops in the c",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF706B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vasiliy likes to rest after a hard work, so you may often meet him in some bar nearby. As all programmers do, he loves the famous drink \"_Beecola_\", which can be bought in _n_ different shops in the c...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Vasiliy 喜欢在辛苦工作后休息，因此你经常能在附近的酒吧遇到他。和所有程序员一样，他热爱一种名为 \"_Beecola_\" 的饮料，这种饮料在城市中有 #cf_span[n] 家商店出售。已知第 #cf_span[i] 家商店中一瓶饮料的价格为 #cf_span[xi] 枚硬币。\n\nVasiliy 计划连续 #cf_span[q] 天购买他最爱的饮料。他知道，在第 #cf_span[i] 天，...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of shops.  \nLet $ X = (x_1, x_2, \\dots, x_n) $ be a sequence of positive integers representing the price of one bottle in each shop.  \nLet $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments