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
#include <vector>
#include <cstdio>
#include <queue>
#define wied(i,a,b) for (int i=a; i<b; i++)
#define fi first
#define se second
#define debug //
using namespace std;
vector <long long> czasy, wynik;
vector <int> glt, nast; //tutaj chcemy miec liczbe nastepnikow
priority_queue <pair <int, pair <int, int> > > kolejka; //dla tekiego d sie stykna - trzeba policzyc recznie
int n, m, d=1e6;
long long zmiana;
int main ()
{
	scanf ("%d %d", &n, &m);
	pair <int , pair <int, int> > para;
	czasy.resize(n+1);
	wynik.resize(d+1);
	nast.resize(n+1);
	nast[0]=1;
	wynik[0]=0;
	czasy[0]=0;
	glt.resize(n+1, 0);
	wied(i,1,n+1) 
	{
		scanf ("%lld", &czasy[i]);
		kolejka.push(make_pair(czasy[i-1]-czasy[i], make_pair(i-1,i)));
		nast[i]=i+1;
	}
	//krok wstepny - laczymy wszystkie dotykajace sie w zerze
	
	wied(i,0,d+1)
	{
		debug ("liczymy sobie wynik dla %d\n", i);
		if (i>0) wynik[i]=wynik[i-1]+zmiana;
		if (!kolejka.empty())
		{
			para=kolejka.top();
			para.fi=-para.fi;
			//debug ("niepusta kolejka: %d %d (%d)\n", para.se.fi, para.se.se, para.fi);
			while ((!kolejka.empty()) && (para.fi==i))
			{
				debug ("niepusta kolejka: %d %d (%d)\n", para.se.fi, para.se.se, para.fi);
				kolejka.pop();
				if ((glt[para.se.fi]>=0) && (glt[para.se.se]>=0))
				{
					debug ("laczymy %d z %d\n", para.se.fi, para.se.se);
					//dodatkowa obsuwa
					debug ("obsuwa zderzeniowa: %lld ",(long long)(glt[para.se.se]+1)*(czasy[para.se.fi]+((long long)(glt[para.se.fi]+1)*i)-czasy[para.se.se]));
					debug ("( %lld *(%lld +( %lld * %d) -%lld ) )\n", (long long)(glt[para.se.se]+1),czasy[para.se.fi],(long long)glt[para.se.fi]+1,i,czasy[para.se.se]);
					debug ("zmiana -= %lld +%lld \n", ((glt[para.se.fi]+1)*(long long)(glt[para.se.fi]))/2,((glt[para.se.se]+1)*(long long)(glt[para.se.se]))/2);
					wynik[i]+=(long long)(glt[para.se.se]+1)*(czasy[para.se.fi]+((long long)(glt[para.se.fi]+1)*i)-czasy[para.se.se]);
					zmiana-=((glt[para.se.fi]+1)*(long long)(glt[para.se.fi]))/2+((glt[para.se.se]+1)*(long long)(glt[para.se.se]))/2;
					glt[para.se.fi]+=glt[para.se.se]+1;
					glt[para.se.se]=-1; //usuwamy to
					zmiana+=((glt[para.se.fi]+1)*(long long)(glt[para.se.fi]))/2;
					debug ("zmiana +=%lld\n", ((glt[para.se.fi]+1)*(long long)(glt[para.se.fi]))/2);
					nast[para.se.fi]=nast[para.se.se];
					if (nast[para.se.fi]<=n)
					{
						debug ("po zlaczeniu wrzucam opcje laczenia: %lld: %d %d\n", (czasy[nast[para.se.fi]]-czasy[para.se.fi]+glt[para.se.fi])/(long long)(1+glt[para.se.fi]), para.se.fi, nast[para.se.fi]);
						kolejka.push(make_pair((-1)*(czasy[nast[para.se.fi]]-czasy[para.se.fi]+glt[para.se.fi])/(long long)(1+glt[para.se.fi]), make_pair(para.se.fi, nast[para.se.fi])));
					}
				}
				para=kolejka.top();
				para.fi=-para.fi;
			}
		}
	}
	/*debug ("nasze wyniki:\n");
	wied(i,0,d+1) debug ("%lld ", wynik[i]);
	debug ("\n");*/
	int y;
	wied(i,0,m)
	{
		scanf ("%d\n", &y);
		printf ("%lld\n", wynik[y]);
	}
	return 0;
}