1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;



vector <unsigned long long> kwiaty;
vector <pair <unsigned long long, unsigned long long> > dni;
unsigned long long tab[500005];
unsigned long long dk[500005];

main()
{
ios_base::sync_with_stdio(0);
int n, m;
unsigned long long wynik;
wynik=0;

cin >> n >> m;

unsigned long long q;

kwiaty.push_back(0);
for (int i=0; i<n; i++)
{
    cin >> q;
    kwiaty.push_back(q);
    tab[i]=0;
    dk[i]=0;
}

tab[n]=dk[n]=0;

unsigned long long x, y;

for (int i=0; i<m; i++)
{
    cin >> y >> x;
    dni.push_back(make_pair(x,y));
}

sort (kwiaty.begin(), kwiaty.end());


unsigned long long p, k, s;

for (int i=0; i<dni.size(); i++)
{

    wynik=0;
    p=0;
    k=kwiaty.size()-2;
    s=(p+k)/2;

    while (!((kwiaty[s+1]*(dni[i].second-dk[s+1]))+tab[s+1]>dni[i].first && (kwiaty[s]*(dni[i].second-dk[s]))+tab[s]<=dni[i].first))
    {
    if ((kwiaty[s]*(dni[i].second-dk[s]))+tab[s]<=dni[i].first) p=s;
    else k=s;
    s=(p+k)/2;
    if (p==k) break;
    if (p+1==k && !((kwiaty[s+1]*(dni[i].second-dk[s+1]))+tab[s+1]>dni[i].first && (kwiaty[s]*(dni[i].second-dk[s]))+tab[s]<=dni[i].first))
        {
        s=kwiaty.size();
        break;
        }
    }

    for (int j=s+1; j<kwiaty.size(); j++)
    {
        wynik+=(kwiaty[j]*(dni[i].second-dk[j]))+tab[j]-dni[i].first;
        tab[j]=dni[i].first;
        dk[j]=dni[i].second;
    }

    cout << wynik << endl;

}



}