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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<iomanip>
#include<fstream>
#include<ctime>
#include<climits>
using namespace std;
typedef vector<int> VI;
typedef long long LL;
typedef pair <int, int> ii;
typedef pair <long double, int> di;
#define pb push_back
const int N = 200005;
const long double eps = 1e-8;
#define DEBUG false

int n, m, d, i, fin[N], r, ind, bat[N], countt, aktDown[N];
LL akt, tab[N], wyn[N], sumAktDown;
set<di> ss;
long double res, last, lastAct[N], tab2[N];
di top;
set<int> done;

int main() {        
	scanf("%d %d", &n, &m);
	for (i=0;i<n;i++) {
		scanf("%lld", &tab[i]);
		fin[i] = i;
		aktDown[i] = 1;
		lastAct[i] = 0.0;
	}
	for (i=n-1;i>0;i--) tab2[i] = tab[i] - tab[i - 1];
	tab2[0] = tab[0];
	for (i=0;i<m;i++) scanf("%d", &bat[i]);
	ss.clear();
	for (i=0;i<n;i++) {
		ss.insert(di(tab2[i], i));		
	}
	for (i=0;i<m;i++) ss.insert(di(bat[i], i + n));
	res = 0;
	sumAktDown = 0;
	last = 0.0;
	countt = 0;
	done.clear();
	while (ss.size() > 0 && countt < m) {
		top = *(ss.begin());
		ss.erase(ss.begin());
		if (done.find(top.second) != done.end()) {
			continue;
		}
		if (DEBUG) printf("entry: %.2LF %d\n", top.first, top.second);
		res += sumAktDown * (top.first - last);		
		last = top.first;
		if (top.second >= n) {
			//printf("%.3LF\n", res);
			wyn[top.second - n] = (LL)(res + 0.5);
			while ((long double)wyn[top.second - n] > res + 0.5) {
				wyn[top.second - n]--;
			}
			while ((long double)wyn[top.second - n] < res - 0.5) {
				wyn[top.second - n]++;
			}
			//printf("%.3LF\n", aa - res);
			countt++;
		} else {
			ind = top.second;
			done.insert(ind);
			if (top.second + 1 < n) {
				r = fin[top.second + 1] - top.second;								
				fin[top.second - aktDown[top.second] + 1] = fin[top.second + 1];
				ind = fin[top.second + 1];
				sumAktDown += aktDown[top.second] * 1LL * r;
				if (done.find(ind) == done.end()) {					
					tab2[ind] -= aktDown[ind] * 1LL * (top.first - lastAct[ind]);
					lastAct[ind] = top.first;
					aktDown[ind] += aktDown[top.second];
					ss.insert(di(top.first + tab2[ind] / aktDown[ind], ind));
				} else {
					aktDown[ind] += aktDown[top.second];
					sumAktDown += aktDown[top.second];
				}
			} else {
				sumAktDown += aktDown[top.second];	
			}
		}		
		if (DEBUG) {
			printf("res: %.2LF,  sumAktDown: %lld\n", res, sumAktDown);
			for (i=0;i<n;i++) printf("%lld ", aktDown[i]);
			printf("\n");
		}
	}	
	for (i=0;i<m;i++) printf("%lld\n", wyn[i]);
}