Return to Question

##B. Lunar New Year And Food Ordering##

The restaurant "Alice's" serves \$n\$ kinds of food. The cost for the \$i\$-th kind is always \$c_i\$. Initially, the restaurant has enough ingredients for serving exactly \$a_i\$ dishes of the \$i\$-th kind. In the New Year's Eve, \$m\$ customers will visit Alice's one after another and the \$j\$-th customer will order \$d_j\$ dishes of the \$t_j\$-th kind of food. The \$(i+1)\$-st customer will only come after the i-th customer is completely served.

Suppose there are \$r_i\$ dishes of the \$i\$-th kind remaining (initially \$r_i = a_i\$). When a customer orders \$1\$ dish of the \$i\$-th kind, the following principles will be processed.

1. If \$r_i > 0\$, the customer will be served exactly \$1\$ dish of the \$i\$-th kind. The cost for the dish is \$c_i\$. Meanwhile, \$r_i\$ will be reduced by \$1\$.
2. Otherwise, the customer will be served \$1\$ dish of the cheapest available kind of food if there are any. If there are multiple cheapest kinds of food, the one with the smallest index among the cheapest will be served. The cost will be the cost for the dish served and the remain for the corresponding dish will be reduced by \$1\$.
3. If there are no more dishes at all, the customer will leave angrily. Therefore, no matter how many dishes are served previously, the cost for the customer is \$0\$.

If the customer doesn't leave after the \$d_j\$ dishes are served, the cost for the customer will be the sum of the cost for these \$d_j\$ dishes.

Please determine the total cost for each of the \$m\$ customers.

###Input###

The first line contains two integers \$n\$ and \$m\$ (\$ 1 ≤ n, m ≤ 10^5\$), representing the number of different kinds of food and the number of customers, respectively.

The second line contains \$n\$ positive integers \$a_1, a_2,\ldots, a_n\$ (\$1 ≤ a_i ≤ 10^7\$), where \$a_i\$ denotes the initial remain of the \$i\$-th kind of dishes.

The third line contains \$n\$ positive integers \$c_1, c_2, \ldots, c_n\$ (\$1 ≤ c_i ≤ 10^6\$), where \$c_i\$ denotes the cost of one dish of the \$i\$-th kind.

The following \$m\$ lines describe the orders of the \$m\$ customers respectively. The \$j\$-th line contains two positive integers \$t_j\$ and \$d_j\$ (\$1 ≤ t_j ≤ n\$, \$1 ≤ d_j ≤ 10^7\$), representing the kind of food and the number of dishes the \$j\$-th customer orders, respectively.

###Output###

Print \$m\$ lines. In the \$j\$-th line print the cost for the \$j\$-th customer.

###Requirements###

• time limit per test: 2 seconds
• memory limit per test: 256 megabytes
• input: standard input
• output: standard output

B. Lunar New Year And Food Ordering

The restaurant "Alice's" serves \$n\$ kinds of food. The cost for the \$i\$-th kind is always \$c_i\$. Initially, the restaurant has enough ingredients for serving exactly \$a_i\$ dishes of the \$i\$-th kind. In the New Year's Eve, \$m\$ customers will visit Alice's one after another and the \$j\$-th customer will order \$d_j\$ dishes of the \$t_j\$-th kind of food. The \$(i+1)\$-st customer will only come after the i-th customer is completely served.

Suppose there are \$r_i\$ dishes of the \$i\$-th kind remaining (initially \$r_i = a_i\$). When a customer orders \$1\$ dish of the \$i\$-th kind, the following principles will be processed.

1. If \$r_i > 0\$, the customer will be served exactly \$1\$ dish of the \$i\$-th kind. The cost for the dish is \$c_i\$. Meanwhile, \$r_i\$ will be reduced by \$1\$.
2. Otherwise, the customer will be served \$1\$ dish of the cheapest available kind of food if there are any. If there are multiple cheapest kinds of food, the one with the smallest index among the cheapest will be served. The cost will be the cost for the dish served and the remain for the corresponding dish will be reduced by \$1\$.
3. If there are no more dishes at all, the customer will leave angrily. Therefore, no matter how many dishes are served previously, the cost for the customer is \$0\$.

If the customer doesn't leave after the \$d_j\$ dishes are served, the cost for the customer will be the sum of the cost for these \$d_j\$ dishes.

Please determine the total cost for each of the \$m\$ customers.

Input

The first line contains two integers \$n\$ and \$m\$ (\$ 1 ≤ n, m ≤ 10^5\$), representing the number of different kinds of food and the number of customers, respectively.

The second line contains \$n\$ positive integers \$a_1, a_2,\ldots, a_n\$ (\$1 ≤ a_i ≤ 10^7\$), where \$a_i\$ denotes the initial remain of the \$i\$-th kind of dishes.

The third line contains \$n\$ positive integers \$c_1, c_2, \ldots, c_n\$ (\$1 ≤ c_i ≤ 10^6\$), where \$c_i\$ denotes the cost of one dish of the \$i\$-th kind.

The following \$m\$ lines describe the orders of the \$m\$ customers respectively. The \$j\$-th line contains two positive integers \$t_j\$ and \$d_j\$ (\$1 ≤ t_j ≤ n\$, \$1 ≤ d_j ≤ 10^7\$), representing the kind of food and the number of dishes the \$j\$-th customer orders, respectively.

Output

Print \$m\$ lines. In the \$j\$-th line print the cost for the \$j\$-th customer.

Requirements

• time limit per test: 2 seconds
• memory limit per test: 256 megabytes
• input: standard input
• output: standard output

Requirement:

The restaurant "Alice's" serves n kinds of food. The cost for the i-th kind is always c[i]. Initially, the restaurant has enough ingredients for serving exactly a[i] dishes of the i-th kind. In the New Year's Eve, m customers will visit Alice's one after another and the j-th customer will order d[j] dishes of the t[j]-th kind of food. The (i+1)-st customer will only come after the i-th customer is completely served.

Suppose there are r[i] dishes of the i-th kind remaining (initially r[i]=a[i]). When a customer orders 1 dish of the i-th kind, the following principles will be processed.

If r[i]>0, the customer will be served exactly 1 dish of the i-th kind. The cost for the dish is c[i]. Meanwhile, r[i] will be reduced by 1. Otherwise, the customer will be served 1 dish of the cheapest available kind of food if there are any. If there are multiple cheapest kinds of food, the one with the smallest index among the cheapest will be served. The cost will be the cost for the dish served and the remain for the corresponding dish will be reduced by 1. If there are no more dishes at all, the customer will leave angrily. Therefore, no matter how many dishes are served previously, the cost for the customer is 0.

If the customer doesn't leave after the d[j] dishes are served, the cost for the customer will be the sum of the cost for these d[j] dishes.

Please determine the total cost for each of the m customers.

Input

The first line contains two integers n and m (1≤n,m≤10^5), representing the number of different kinds of food and the number of customers, respectively.

The second line contains n positive integers a[1],a[2],…,a[n] (1≤**a[i]**≤10^7), where a[i] denotes the initial remain of the i-th kind of dishes.

The third line contains n positive integers c[1],c[2],…,c[n] (1≤**c[i]**≤10^6), where c[i] denotes the cost of one dish of the i-th kind.

The following m lines describe the orders of the m customers respectively. The j-th line contains two positive integers t[j] and d[j] (1≤**t[j]≤n, 1≤d[j]**≤10^7), representing the kind of food and the number of dishes the j-th customer orders, respectively.

Output

Print m lines. In the j-th line print the cost for the j-th customer.

##B. Lunar New Year And Food Ordering##

The restaurant "Alice's" serves \$n\$ kinds of food. The cost for the \$i\$-th kind is always \$c_i\$. Initially, the restaurant has enough ingredients for serving exactly \$a_i\$ dishes of the \$i\$-th kind. In the New Year's Eve, \$m\$ customers will visit Alice's one after another and the \$j\$-th customer will order \$d_j\$ dishes of the \$t_j\$-th kind of food. The \$(i+1)\$-st customer will only come after the i-th customer is completely served.

Suppose there are \$r_i\$ dishes of the \$i\$-th kind remaining (initially \$r_i = a_i\$). When a customer orders \$1\$ dish of the \$i\$-th kind, the following principles will be processed.

1. If \$r_i > 0\$, the customer will be served exactly \$1\$ dish of the \$i\$-th kind. The cost for the dish is \$c_i\$. Meanwhile, \$r_i\$ will be reduced by \$1\$.
2. Otherwise, the customer will be served \$1\$ dish of the cheapest available kind of food if there are any. If there are multiple cheapest kinds of food, the one with the smallest index among the cheapest will be served. The cost will be the cost for the dish served and the remain for the corresponding dish will be reduced by \$1\$.
3. If there are no more dishes at all, the customer will leave angrily. Therefore, no matter how many dishes are served previously, the cost for the customer is \$0\$.

If the customer doesn't leave after the \$d_j\$ dishes are served, the cost for the customer will be the sum of the cost for these \$d_j\$ dishes.

Please determine the total cost for each of the \$m\$ customers.

###Input###

The first line contains two integers \$n\$ and \$m\$ (\$ 1 ≤ n, m ≤ 10^5\$), representing the number of different kinds of food and the number of customers, respectively.

The second line contains \$n\$ positive integers \$a_1, a_2,\ldots, a_n\$ (\$1 ≤ a_i ≤ 10^7\$), where \$a_i\$ denotes the initial remain of the \$i\$-th kind of dishes.

The third line contains \$n\$ positive integers \$c_1, c_2, \ldots, c_n\$ (\$1 ≤ c_i ≤ 10^6\$), where \$c_i\$ denotes the cost of one dish of the \$i\$-th kind.

The following \$m\$ lines describe the orders of the \$m\$ customers respectively. The \$j\$-th line contains two positive integers \$t_j\$ and \$d_j\$ (\$1 ≤ t_j ≤ n\$, \$1 ≤ d_j ≤ 10^7\$), representing the kind of food and the number of dishes the \$j\$-th customer orders, respectively.

###Output###

Print \$m\$ lines. In the \$j\$-th line print the cost for the \$j\$-th customer.

###Requirements###

• time limit per test: 2 seconds
• memory limit per test: 256 megabytes
• input: standard input
• output: standard output

#include <bits/stdc++.h>
using namespace std;
struct food
{
    long long stock, cost;
} v[100001];
int main()
{
    struct order
    {
        long type;
        long long dishes;
    } cust; ///cust = customer
    struct minim
    {
        long pos=0;
        long value=2147483647;
    } mn;
    long long i,n,m,cost,d,j;
    cin >> n >> m;
    for (i=1; i<=n; i++)
    {
        cin >> v[i].stock;
    }
    for (i=1; i<=n; i++)
    {
        cin >> v[i].cost;
        if (v[i].cost < mn.value && v[i].stock)
        {
            mn.value = v[i].cost;
            mn.pos = i;
        }
    }
    for (i=1; i<=m; i++)
    {
        cost = 0;
        cin >> cust.type >> cust.dishes;
        d=v[cust.type].stock;
        v[cust.type].stock -= cust.dishes;
        if (v[cust.type].stock >= 0)
            cost = v[cust.type].cost * cust.dishes;
        else
        {
            cost = v[cust.type].cost * (cust.dishes + v[cust.type].stock);
            v[cust.type].stock = 0;
            cust.dishes -= d;
            while (cust.dishes)
            {
                if (cust.dishes > v[mn.pos].stock)
                {
                    cust.dishes = cust.dishes - v[mn.pos].stock;
                    cost += v[mn.pos].stock * v[mn.pos].cost;
                    v[mn.pos].stock = 0;
                    for (j=1; j<=n; j++)
                    {
                        if (v[j].cost <= mn.value && v[j].stock)
                        {
                            mn.value = v[j].cost;
                            mn.pos = j;
                            break;
                        }
                    }
                    if (v[mn.pos].stock == 0)
                    {
                        mn.pos=0;
                        mn.value = 2147483647;
                        for (j=1; j<=n; j++)
                        {
                            if (v[j].cost <= mn.value && v[j].stock)
                            {
                                mn.value = v[j].cost;
                                mn.pos = j;
                            }
                        }
                    }
                    if (mn.value == 2147483647 && cust.dishes)
                    {
                        cost = 0;
                        cust.dishes = 0;
                    }
                }
                else
                {
                    cost += v[mn.pos].cost * cust.dishes;
                    v[mn.pos].stock -= cust.dishes;
                    cust.dishes = 0;
                }
            }
        }
        cout << cost << "\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
struct food
{
    long long stock, cost;
} v[100005];
struct sorted_food
{
    long long type, cost;
} s[100005];
bool compare (sorted_food lhs, sorted_food rhs)
{
    return (lhs.cost < rhs.cost && lhs.cost && rhs.cost);
}
int main()
{
    struct order
    {
        long type;
        long long dishes;
    } cust; ///cust = customer
    struct minim
    {
        long pos=0;
        long value=2147483647;
    } mn;
    long long i,n,m,cost,d,j,k=1;
    cin >> n >> m;
    for (i=1; i<=n; i++)
    {
        cin >> v[i].stock;
    }
    for (i=1; i<=n; i++)
    {
        cin >> v[i].cost;
        s[k].cost = v[i].cost;
        s[k].type = i;
        k++;
        if (v[i].cost < mn.value && v[i].stock)
        {
            mn.value = v[i].cost;
            mn.pos = i;
        }
    }
    sort(s + 1, s + k, compare);
    for (i=1; i<=m; i++)
    {
        cost = 0;
        cin >> cust.type >> cust.dishes;
        d=v[cust.type].stock;
        v[cust.type].stock -= cust.dishes;
        if (v[cust.type].stock >= 0)
            cost = v[cust.type].cost * cust.dishes;
        else
        {
            cost = v[cust.type].cost * (cust.dishes + v[cust.type].stock);
            v[cust.type].stock = 0;
            cust.dishes -= d;
            while (cust.dishes)
            {
                if (cust.dishes > v[mn.pos].stock)
                {
                    cust.dishes = cust.dishes - v[mn.pos].stock;
                    cost += v[mn.pos].stock * v[mn.pos].cost;
                    v[mn.pos].stock = 0;
                    mn.value = 2147483647;
                    mn.pos = 0;
                    for (j=1; j<=k; j++)
                    {
                        if (v[s[j].type].cost <= mn.value && v[s[j].type].stock)
                        {
                            mn.value = v[s[j].type].cost;
                            mn.pos = s[j].type;
                            break;
                        }
                    }
                    if (mn.value == 2147483647 && cust.dishes)
                    {
                        cost = 0;
                        cust.dishes = 0;
                    }
                }
                else
                {
                    cost += v[mn.pos].cost * cust.dishes;
                    v[mn.pos].stock -= cust.dishes;
                    cust.dishes = 0;
                }
            }
        }
        cout << cost << "\n";
    }
}

Edit: definitely the code gets stuck somewhere, I just replaced my old and inefficient search for a sorted array and the results are the same.