#include<cstdio> #include <algorithm> #include <string.h> using namespace std; #define N 200000 #define D_MAX 1000000 #define D_MAX_TAB 1000010 long long int t[N + 10]; long long int d[N + 10]; long long int e[N + 10]; long long int wyniki[D_MAX_TAB]; long long int liczba_zer[D_MAX_TAB]; long long int trojkaty[N + 10]; long long int n; void inicjuj_trojkaty() { for (int i = 1; i < N + 10; i++) { trojkaty[i] = trojkaty[i - 1] + i; } } void licz_jedna(long long int d) { if (wyniki[d] != -1) { return; } long long int s = 0; wyniki[d] = 0; for (int j = 0; j < n; j++) { if (d + s <= t[j]) { s = t[j]; liczba_zer[d]++; } else { wyniki[d] += d + s - t[j]; s += d; } } } void licz_zakres(long long int min_1, long long int max_1) { long long int min = e[min_1]; long long int max = e[max_1]; if (max < min) { return; } if (min == max) { licz_jedna(min); return; } licz_jedna(min); licz_jedna(max); if (max_1 - min_1 > 1) { bool czy_liczyc_dalej = true; if (liczba_zer[min] == liczba_zer[max]) { if (wyniki[max] - wyniki[min] == trojkaty[n - liczba_zer[min]] * (max - min)) { for (int i = min_1 + 1; i < max_1; i++) { wyniki[e[i]] = wyniki[min] + trojkaty[n - liczba_zer[min]] * (e[i] - min); liczba_zer[e[i]] = liczba_zer[min]; //wyniki[i] = wyniki[min] + trojkaty[n - liczba_zer[min]] * (i - min); //liczba_zer[i] = liczba_zer[min]; } czy_liczyc_dalej = false; } } if (czy_liczyc_dalej) { if (max_1 != (max_1 + min_1) / 2) { licz_zakres(min_1, (max_1 + min_1) / 2); } if (min_1 != 1 + (max_1 + min_1) / 2) { licz_zakres(1 + (max_1 + min_1) / 2, max_1); } } } } int main() { inicjuj_trojkaty(); long long int m; memset(&wyniki, -1L, D_MAX_TAB * sizeof(long long int)); scanf("%lld %lld", &n, &m); for (int i = 0; i < n; i++){ scanf("%lld", &t[i]); } for (int i = 0; i < m; i++) { scanf("%lld", &d[i]); e[i] = d[i]; } sort(e, e + m); licz_zakres(0, m - 1); for (int i = 0; i < m; i++) { printf("%lld\n", wyniki[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 106 107 108 109 110 111 112 113 114 115 116 117 118 119 | #include<cstdio> #include <algorithm> #include <string.h> using namespace std; #define N 200000 #define D_MAX 1000000 #define D_MAX_TAB 1000010 long long int t[N + 10]; long long int d[N + 10]; long long int e[N + 10]; long long int wyniki[D_MAX_TAB]; long long int liczba_zer[D_MAX_TAB]; long long int trojkaty[N + 10]; long long int n; void inicjuj_trojkaty() { for (int i = 1; i < N + 10; i++) { trojkaty[i] = trojkaty[i - 1] + i; } } void licz_jedna(long long int d) { if (wyniki[d] != -1) { return; } long long int s = 0; wyniki[d] = 0; for (int j = 0; j < n; j++) { if (d + s <= t[j]) { s = t[j]; liczba_zer[d]++; } else { wyniki[d] += d + s - t[j]; s += d; } } } void licz_zakres(long long int min_1, long long int max_1) { long long int min = e[min_1]; long long int max = e[max_1]; if (max < min) { return; } if (min == max) { licz_jedna(min); return; } licz_jedna(min); licz_jedna(max); if (max_1 - min_1 > 1) { bool czy_liczyc_dalej = true; if (liczba_zer[min] == liczba_zer[max]) { if (wyniki[max] - wyniki[min] == trojkaty[n - liczba_zer[min]] * (max - min)) { for (int i = min_1 + 1; i < max_1; i++) { wyniki[e[i]] = wyniki[min] + trojkaty[n - liczba_zer[min]] * (e[i] - min); liczba_zer[e[i]] = liczba_zer[min]; //wyniki[i] = wyniki[min] + trojkaty[n - liczba_zer[min]] * (i - min); //liczba_zer[i] = liczba_zer[min]; } czy_liczyc_dalej = false; } } if (czy_liczyc_dalej) { if (max_1 != (max_1 + min_1) / 2) { licz_zakres(min_1, (max_1 + min_1) / 2); } if (min_1 != 1 + (max_1 + min_1) / 2) { licz_zakres(1 + (max_1 + min_1) / 2, max_1); } } } } int main() { inicjuj_trojkaty(); long long int m; memset(&wyniki, -1L, D_MAX_TAB * sizeof(long long int)); scanf("%lld %lld", &n, &m); for (int i = 0; i < n; i++){ scanf("%lld", &t[i]); } for (int i = 0; i < m; i++) { scanf("%lld", &d[i]); e[i] = d[i]; } sort(e, e + m); licz_zakres(0, m - 1); for (int i = 0; i < m; i++) { printf("%lld\n", wyniki[d[i]]); } return 0; } |