HDU 4907 Task schedule

Description

有一台机器，并且给你这台机器的工作表，工作表上有n个任务，机器在ti时间执行第i个任务，1秒即可完成1个任务。 

有m个询问，每个询问有一个数字q，表示如果在q时间有一个工作表之外的任务请求，请计算何时这个任务才能被执行。 

机器总是按照工作表执行，当机器空闲时立即执行工作表之外的任务请求。

Input

输入的第一行包含一个整数T， 表示一共有T组测试数据。 

对于每组测试数据： 

第一行是两个数字n, m，表示工作表里面有n个任务, 有m个询问； 

第二行是n个不同的数字t1, t2, t3....tn，表示机器在ti时间执行第i个任务。 

接下来m行，每一行有一个数字q，表示在q时间有一个工作表之外的任务请求。 

特别提醒：m个询问之间是无关的。 

[Technical Specification] 

1. T <= 50 

2. 1 <= n, m <= 10^5 

3. 1 <= ti <= 2*10^5, 1 <= i <= n 

4. 1 <= q <= 2*10^5 

Output

对于每一个询问，请计算并输出该任务何时才能被执行，每个询问输出一行。

Sample Input

1

5 5

1 2 3 5 6

1

2

3

4

5

Sample Output

4

4

4

4

7

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define fi first
#define se second
#define mp(i,j) make_pair(i,j)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const int read()
{
  char ch = getchar();
  while (ch<'0' || ch>'9') ch = getchar();
  int x = ch - '0';
  while ((ch = getchar()) >= '0'&&ch <= '9') x = x * 10 + ch - '0';
  return x;
}
int T, n, m, x, r[N];

int main()
{
  T = read();
  while (T--)
  {
    scanf("%d%d", &n, &m);
    memset(r, 0, sizeof(r));
    while (n--) { scanf("%d", &x), r[x] = 1; }
    per(i, N - 1, 1) if (r[i]) r[i] = r[i + 1]; else r[i] = i;
    while (m--) scanf("%d", &x), printf("%d\n", r[x]);
  }
  return 0;
}