FZU2077——暴力技巧——The tallest tree

lzs种了n棵树，每棵树每天长高一定的高度。某一天，lzs想知道树长得怎么样了，你能求出那一天最高的树有多高吗？

Input

有多组测试数据，每组数据第一行输入两个整数n,m(1<=n,m<=100000)，接下来n行，每行两个整数a,b(0<=a,b<=100000)，表示第i棵树在第0天的高度以及每天生长的高度。接下来m行，每行一个整数x(0<=x<=100000)，表示询问第x天最高的树有多高。

Output

对于每个询问输出一行，为当天最高的树的高度。

Sample Input

1 3 10 4 1 2 3

Sample Output

14 18 22

/*
先根据v进行从大到小排序，使得如果一旦高度达到，就只要判断前面的几个
离线对b根据day进行排序，每次更新index，处理完之后返回原来的序号
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX = 100000 + 10;
struct edge{
    int h, v;
}a[MAX];

struct edge1{
    int d, h, id;
}b[MAX];
bool cmp(edge i, edge j)
{
    if(i.v == j.v) return i.h > j.h;
    return i.v > j.v;
}

bool cmp1(edge1 i, edge1 j)
{
    return i.d < j.d;
}

bool cmp2(edge1 i, edge1 j)
{
    return i.id < j.id;
}
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m)){
        for(int i = 1; i <= n ;i++){
            scanf("%d%d", &a[i].h, &a[i].v);
        }
        sort(a + 1, a + n + 1, cmp);
        for(int i = 1; i <= m ;i++){
            scanf("%d", &b[i].d);
            b[i].id = i;
        }
        sort(b + 1, b + m + 1, cmp1);
        int max1 = 0, index = 0;
        for(int i = 1; i <= n ;i++){
            if(a[i].h >= max1){
                max1 = a[i].h;
                index = i;
            }
        }
        int day = index;
        for(int i = 1; i <= m ;i++){
            for(int j = 1; j <= day; j++){
                int temp = b[i].d * a[j].v + a[j].h ;
                if(temp >= max1){
                    index = j;
                    max1 = temp;
                }
            }
            day = index;
            b[i].h = max1;
        }
        sort(b + 1, b + m + 1, cmp2);
        for(int i = 1; i <= m ;i++)
            printf("%d
", b[i].h);
        }
    return 0;
}