Task schedule

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 387 Accepted Submission(s): 193

Problem 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

Sample Output

Source

BestCoder Round #3

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-10
///#define LL __int64
#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?0:x)

const int maxn = 201000;

using namespace std;

int vis[maxn];
int num[maxn];

int main()
{
    int T;
    cin >>T;
    while(T--)
    {
        int n, m;
        cin >>n>>m;
        memset(vis, 0, sizeof(vis));
        int x;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&x);
            vis[x] = 1;
        }
        int now;
        for(int i = maxn-1; i >= 1; i--)
        {
            if(!vis[i])
            {
                now = i;
                num[i] = now;
                continue;
            }
            num[i] = now;
        }
        while(m--)
        {
            scanf("%d",&x);
            printf("%d
",num[x]);
        }
    }
    return 0;
}

B.统计左右比m大的个数，然后求和。

BestCoder Sequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 258 Accepted Submission(s): 108

Problem Description

Mr Potato is a coder.
Mr Potato is the BestCoder.

One night, an amazing sequence appeared in his dream. Length of this sequence is odd, the median number is M, and he named this sequence as Bestcoder Sequence.

As the best coder, Mr potato has strong curiosity, he wonder the number of consecutive sub-sequences which are bestcoder sequences in a given permutation of 1 ~ N.

Input

Input contains multiple test cases.
For each test case, there is a pair of integers N and M in the first line, and an permutation of 1 ~ N in the second line.

[Technical Specification]
1. 1 <= N <= 40000
2. 1 <= M <= N

Output

For each case, you should output the number of consecutive sub-sequences which are the Bestcoder Sequences.

Sample Input

Sample Output

1
3

Hint
For the second case, {3},{5,3,2},{4,5,3,2,1} are Bestcoder Sequence.

Source

BestCoder Round #3

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-10
#define LL __int64
///#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?0:x)

const int maxn = 101000;

using namespace std;

int num[maxn];
LL sum1[maxn];
LL sum2[maxn];
int main()
{
    int n, m;
    while(cin >>n>>m)
    {
        memset(sum1, 0, sizeof(sum1));
        memset(sum2, 0, sizeof(sum2));
        int s;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&num[i]);
            if(num[i] == m) s = i;
        }
        int cnt = 0;
        int pp = 40000;
        sum1[pp] = 1;
        for(int i = s-1; i >= 1; i--)
        {
            if(num[i] > m) cnt++;
            else if(num[i] < m) cnt--;
            sum1[cnt+pp]++;
        }
        cnt = 0;
        LL ans = 0;
        ans += sum1[pp];
        for(int i = s+1; i <= n; i++)
        {
            if(num[i] > m) cnt++;
            else if(num[i] < m)cnt--;
            sum2[cnt+pp]++;
            ans += sum1[pp-cnt];
        }
        cout<<ans<<endl;
    }
    return 0;
}