#include <stdio.h> #include <queue> //#define sufit(a, b) (((a)+(b)-1)/(b)) using namespace std; struct czas { long long czas; // czas jaki potrzeba do polaczenia grup int indx; // index long long modulo; }; inline bool operator<(const czas &a, const czas &b) { return (a.czas > b.czas); } long long sufit(long long a, long long b) { return (a + b - 1) / b; } int main(void) { int n, m; static long long t[200002]; static int d[200000]; static long long r[1000001]; static int s[200000]; // sklejone long long obecne_rozwiazanie; long long delta; priority_queue<czas> PQ; scanf("%d%d", &n, &m); s[0] = 1; for (int i = 1; i <= n; i++) { scanf("%lld", &t[i]); s[i] = 1; } t[n+1] = 1000000000000000000LL; for (int i = 0; i < m; i++) scanf("%d", &d[i]); r[0] = obecne_rozwiazanie = delta = 0; for (int i = 0; i < n; i++) { czas C; C.indx = i; C.czas = t[i+1] - t[i]; C.modulo = 0; PQ.push(C); } for (int i = 1; i <= 1000000; i++) { while (!PQ.empty() && PQ.top().czas < i) { czas C = PQ.top(); PQ.pop(); if (s[C.indx] != -1) { int stare1 = s[C.indx]; int stare2 = s[C.indx + s[C.indx]]; obecne_rozwiazanie -= C.modulo * stare2; s[C.indx + s[C.indx]] = -1; s[C.indx] += stare2; //printf("Czas z kolejki %lld\n", C.czas); //printf("W czasie %d skleilem grupe %d, ma ona teraz dlugosc %d\n", i, C.indx, s[C.indx]); czas CN; CN.indx = C.indx; CN.czas = (t[C.indx + s[C.indx]] - t[C.indx]) / s[C.indx]; CN.modulo = (t[C.indx + s[C.indx]] - t[C.indx]) % s[C.indx]; PQ.push(CN); delta -= (long long) stare1 * (stare1 - 1) / 2; delta -= (long long) stare2 * (stare2 - 1) / 2; delta += (long long)(stare1 + stare2) * (stare1 + stare2 -1) / 2; } } obecne_rozwiazanie += delta; r[i] = obecne_rozwiazanie; } for (int i = 0; i < m; i++) { printf("%lld\n", r[d[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 101 102 103 104 105 | #include <stdio.h> #include <queue> //#define sufit(a, b) (((a)+(b)-1)/(b)) using namespace std; struct czas { long long czas; // czas jaki potrzeba do polaczenia grup int indx; // index long long modulo; }; inline bool operator<(const czas &a, const czas &b) { return (a.czas > b.czas); } long long sufit(long long a, long long b) { return (a + b - 1) / b; } int main(void) { int n, m; static long long t[200002]; static int d[200000]; static long long r[1000001]; static int s[200000]; // sklejone long long obecne_rozwiazanie; long long delta; priority_queue<czas> PQ; scanf("%d%d", &n, &m); s[0] = 1; for (int i = 1; i <= n; i++) { scanf("%lld", &t[i]); s[i] = 1; } t[n+1] = 1000000000000000000LL; for (int i = 0; i < m; i++) scanf("%d", &d[i]); r[0] = obecne_rozwiazanie = delta = 0; for (int i = 0; i < n; i++) { czas C; C.indx = i; C.czas = t[i+1] - t[i]; C.modulo = 0; PQ.push(C); } for (int i = 1; i <= 1000000; i++) { while (!PQ.empty() && PQ.top().czas < i) { czas C = PQ.top(); PQ.pop(); if (s[C.indx] != -1) { int stare1 = s[C.indx]; int stare2 = s[C.indx + s[C.indx]]; obecne_rozwiazanie -= C.modulo * stare2; s[C.indx + s[C.indx]] = -1; s[C.indx] += stare2; //printf("Czas z kolejki %lld\n", C.czas); //printf("W czasie %d skleilem grupe %d, ma ona teraz dlugosc %d\n", i, C.indx, s[C.indx]); czas CN; CN.indx = C.indx; CN.czas = (t[C.indx + s[C.indx]] - t[C.indx]) / s[C.indx]; CN.modulo = (t[C.indx + s[C.indx]] - t[C.indx]) % s[C.indx]; PQ.push(CN); delta -= (long long) stare1 * (stare1 - 1) / 2; delta -= (long long) stare2 * (stare2 - 1) / 2; delta += (long long)(stare1 + stare2) * (stare1 + stare2 -1) / 2; } } obecne_rozwiazanie += delta; r[i] = obecne_rozwiazanie; } for (int i = 0; i < m; i++) { printf("%lld\n", r[d[i]]); } return 0; } |