#include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 200200; int n,m; ll t[N]; pii d[N]; int nxt[N], prv[N], el[N]; int used[N]; ll ret[N]; struct data { ll join_t; int le, ri; data (ll jt, int l, int r) { join_t = jt; le=l; ri=r; } bool operator< (const data &dd) const { if (join_t != dd.join_t) return join_t > dd.join_t; return mp(le,ri) < mp(dd.le, dd.ri); } }; inline ll bin(int x) { return 1LL * x * (x-1) / 2; } int main() { scanf("%d%d", &n, &m); FORI(i,n) scanf("%lld", &t[i]); FOR(i,m) scanf("%d", &d[i].fi); FOR(i,m) d[i].se = i; sort(d,d+m); priority_queue<data> Q; ll total = 0, mult = 0; el[0]=1; FORI(i,n) { el[i] = 1; nxt[i-1] = i; prv[i] = i-1; Q.push(data(t[i]-t[i-1], i-1, i)); } prv[0] = -1; nxt[n] = -1; int j=0; while (!Q.empty()) { data cur = Q.top(); Q.pop(); if (used[cur.ri] || used[cur.le]) continue; used[cur.ri] = true; //printf("joining %d and %d\n", cur.le, cur.ri); // update result while (j < m && d[j].fi < cur.join_t) { //for (int u=0; u!=-1; u=nxt[u]) printf("%d ", el[u]); printf("\n"); ret[d[j].se] = mult * d[j].fi - total; j++; } total += (t[cur.ri]-t[cur.le]) * el[cur.ri]; mult -= bin(el[cur.le]) + bin(el[cur.ri]); mult += bin(el[cur.le] + el[cur.ri]); //printf("time = %lld, total = %lld, mult = %lld\n", cur.join_t, total, mult); // remove node el[cur.le] += el[cur.ri]; nxt[cur.le] = nxt[cur.ri]; if (nxt[cur.ri] != -1) { prv[nxt[cur.ri]] = cur.le; cur.ri = nxt[cur.ri]; cur.join_t = (t[cur.ri]-t[cur.le]+el[cur.le]-1) / el[cur.le]; //printf("%d (%lld; %d) and %d (%lld) at time %lld\n", cur.le, t[cur.le], el[cur.le], cur.ri, t[cur.ri], cur.join_t); Q.push(cur); } } while (j < m) { ret[d[j].se] = mult * d[j].fi - total; j++; } FOR(i,m) printf("%lld\n", ret[i]); return 0; }
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 | #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 200200; int n,m; ll t[N]; pii d[N]; int nxt[N], prv[N], el[N]; int used[N]; ll ret[N]; struct data { ll join_t; int le, ri; data (ll jt, int l, int r) { join_t = jt; le=l; ri=r; } bool operator< (const data &dd) const { if (join_t != dd.join_t) return join_t > dd.join_t; return mp(le,ri) < mp(dd.le, dd.ri); } }; inline ll bin(int x) { return 1LL * x * (x-1) / 2; } int main() { scanf("%d%d", &n, &m); FORI(i,n) scanf("%lld", &t[i]); FOR(i,m) scanf("%d", &d[i].fi); FOR(i,m) d[i].se = i; sort(d,d+m); priority_queue<data> Q; ll total = 0, mult = 0; el[0]=1; FORI(i,n) { el[i] = 1; nxt[i-1] = i; prv[i] = i-1; Q.push(data(t[i]-t[i-1], i-1, i)); } prv[0] = -1; nxt[n] = -1; int j=0; while (!Q.empty()) { data cur = Q.top(); Q.pop(); if (used[cur.ri] || used[cur.le]) continue; used[cur.ri] = true; //printf("joining %d and %d\n", cur.le, cur.ri); // update result while (j < m && d[j].fi < cur.join_t) { //for (int u=0; u!=-1; u=nxt[u]) printf("%d ", el[u]); printf("\n"); ret[d[j].se] = mult * d[j].fi - total; j++; } total += (t[cur.ri]-t[cur.le]) * el[cur.ri]; mult -= bin(el[cur.le]) + bin(el[cur.ri]); mult += bin(el[cur.le] + el[cur.ri]); //printf("time = %lld, total = %lld, mult = %lld\n", cur.join_t, total, mult); // remove node el[cur.le] += el[cur.ri]; nxt[cur.le] = nxt[cur.ri]; if (nxt[cur.ri] != -1) { prv[nxt[cur.ri]] = cur.le; cur.ri = nxt[cur.ri]; cur.join_t = (t[cur.ri]-t[cur.le]+el[cur.le]-1) / el[cur.le]; //printf("%d (%lld; %d) and %d (%lld) at time %lld\n", cur.le, t[cur.le], el[cur.le], cur.ri, t[cur.ri], cur.join_t); Q.push(cur); } } while (j < m) { ret[d[j].se] = mult * d[j].fi - total; j++; } FOR(i,m) printf("%lld\n", ret[i]); return 0; } |