#include <vector> #include <set> #include <cstdio> #include <utility> typedef std::pair<int, int> PII; const int M = 201013; const int Q = 1001013; long long t[M], sw[M], ret[M]; int nw[M], dd[M]; int n; long long getA(int i) { return ((long long)nw[i]) * (nw[i] + 1) / 2; } long long getB(int i) { return nw[i] * t[i] - sw[i]; } void lacz(int i, int j) { nw[i] += nw[j] + 1; sw[i] += sw[j] + t[j]; int x = i + nw[i] + 1; if (x > n) dd[i] = -1; else dd[i] = std::min<long long>(Q, (t[x] - t[i] + nw[i]) / (nw[i] + 1)); if (dd[i] >= Q) dd[i] = -1; //printf("%d :: %lld :: %d %lld %d\n", i, t[i], nw[i], sw[i], dd[i]); } int main() { int m; scanf("%d %d",&n,&m); std::set<PII> e; for (int i = 0; i < n; i++) { scanf("%lld", &t[i+1]); dd[i] = std::min<long long>(Q, t[i+1] - t[i]); if (dd[i] >= Q) dd[i] = -1; else e.insert(PII(dd[i], -(i+1))); } dd[n] = -1; for (int i = 0; i < m; i++) { int d; scanf("%d", &d); e.insert(PII(d, i)); } long long A = 0, B = 0; while (!e.empty()) { int d = e.begin()->first; int i = e.begin()->second; e.erase(e.begin()); if (i >= 0) { //printf("%lld * %d + %lld\n",A,d,B); ret[i] = A*d + B; } else { i = -i-1; int j = i + 1 + nw[i]; A -= getA(i); B -= getB(i); A -= getA(j); B -= getB(j); if (dd[j] >= 0) e.erase(PII(dd[j], -(j+1))); lacz(i, j); A += getA(i); B += getB(i); if (dd[i] >= 0) e.insert(PII(dd[i], -(i+1))); } } for (int i = 0; i < m; i++) 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 | #include <vector> #include <set> #include <cstdio> #include <utility> typedef std::pair<int, int> PII; const int M = 201013; const int Q = 1001013; long long t[M], sw[M], ret[M]; int nw[M], dd[M]; int n; long long getA(int i) { return ((long long)nw[i]) * (nw[i] + 1) / 2; } long long getB(int i) { return nw[i] * t[i] - sw[i]; } void lacz(int i, int j) { nw[i] += nw[j] + 1; sw[i] += sw[j] + t[j]; int x = i + nw[i] + 1; if (x > n) dd[i] = -1; else dd[i] = std::min<long long>(Q, (t[x] - t[i] + nw[i]) / (nw[i] + 1)); if (dd[i] >= Q) dd[i] = -1; //printf("%d :: %lld :: %d %lld %d\n", i, t[i], nw[i], sw[i], dd[i]); } int main() { int m; scanf("%d %d",&n,&m); std::set<PII> e; for (int i = 0; i < n; i++) { scanf("%lld", &t[i+1]); dd[i] = std::min<long long>(Q, t[i+1] - t[i]); if (dd[i] >= Q) dd[i] = -1; else e.insert(PII(dd[i], -(i+1))); } dd[n] = -1; for (int i = 0; i < m; i++) { int d; scanf("%d", &d); e.insert(PII(d, i)); } long long A = 0, B = 0; while (!e.empty()) { int d = e.begin()->first; int i = e.begin()->second; e.erase(e.begin()); if (i >= 0) { //printf("%lld * %d + %lld\n",A,d,B); ret[i] = A*d + B; } else { i = -i-1; int j = i + 1 + nw[i]; A -= getA(i); B -= getB(i); A -= getA(j); B -= getB(j); if (dd[j] >= 0) e.erase(PII(dd[j], -(j+1))); lacz(i, j); A += getA(i); B += getB(i); if (dd[i] >= 0) e.insert(PII(dd[i], -(i+1))); } } for (int i = 0; i < m; i++) printf("%lld\n", ret[i]); return 0; } |