eqal_range

Luogu
IDLGB4362
Time1000ms
Memory512MB
DifficultyP2
二分排序
给定一个数列 $a = [a_1, a_2, \dots, a_n]$,有 $q$ 次询问,每次询问给出一个整数 $x$,你要回答:序列 $a$ 里最小的比 $x$ 大的数是多少?$a$ 里最大的比 $x$ 小的数是多少? ## Input 第一行是两个整数,表示序列长度 $n$ 和询问次数 $q$。 第二行有 $n$ 个整数表示 $a_1, a_2, \dots a_n$。 接下来 $q$ 行,每行一个整数 $x$ 表示查询的数字。 ## Output 对每次查询,输出两个整数 $u,v$,依次表示数列 $a$ 里最小的比 $x$ 大的数和最大的比 $x$ 小的数。 如果相应的数不存在,在对应位置输出 $-1$。 [samples] ## Note 对全部的测试数据,保证 $1 \leq n,q \leq 10^6$,$1 \leq a_i, x \leq 10^9$。 **请注意大量数据读入对程序效率造成的影响**。
Samples
Input #1
5 3
1 2 3 4 5
1
3
5
Output #1
2 -1
4 2
-1 4
API Response (JSON)
{
  "problem": {
    "name": "eqal_range",
    "description": {
      "content": "给定一个数列 $a = [a_1, a_2, \\dots, a_n]$,有 $q$ 次询问,每次询问给出一个整数 $x$,你要回答:序列 $a$ 里最小的比 $x$ 大的数是多少?$a$ 里最大的比 $x$ 小的数是多少?",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4362"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个数列 $a = [a_1, a_2, \\dots, a_n]$,有 $q$ 次询问,每次询问给出一个整数 $x$,你要回答:序列 $a$ 里最小的比 $x$ 大的数是多少?$a$ 里最大的比 $x$ 小的数是多少?\n\n## Input\n\n第一行是两个整数,表示序列长度 $n$ 和询问次数 $q$。  \n第二行有 $n$ 个整数表示 $a_1, a_2, \\dots a_n$。  \n接下来 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments