#include <cstdio> #include <cmath> #include <cassert> #include <string> #include <algorithm> #include <functional> //#define DEBUG #ifdef DEBUG #define D(x); x #else #define D(x); #endif #define LL long long #define LLA (long long []) using namespace std; LL k[200002]; // n LL p[200002]; // m LL o[200002]; void print_input(int n, int m) { for(int i = 0; i < n; i++) { printf("%lld ", k[i]); } printf("\n"); for(int i = 0; i < m; i++) { printf("%lld ", p[i]); } printf("\n"); } void print_output(int m) { for(int i = 0; i < m; i++) { printf("%lld ", o[i]); } printf("\n"); } void zap(int n, int m) { D(printf("---\nZAP for arrays (%d, %d):\n", n, m);); D(print_input(n, m);); for(int j = 0; j < m; j++) { o[j] = 0L; LL time = p[j]; LL prevk = 0L; LL prev_wait = 0L; D(printf("--- p[%d] = %lld ---\n", j, p[j]);); for(int i = 0; i < n; i++) { LL diff = k[i] - (prevk + prev_wait); LL wait = 0; if(time > diff) wait = time - diff; o[j] += wait; D(printf("k[%d] comes @%lld, has %lld buffer and waits %lld (total %lld)\n", i, k[i], diff, wait, o[j]);); prevk = k[i]; prev_wait = wait; } } D(print_output(m);); } #ifdef DEBUG bool test(LL A[], int a, LL B[], int b, LL C[]) { std::copy(A, A + a, k); std::copy(B, B + b, p); zap(a, b); for(int i = 0; i < b; i++) { if(o[i] != C[i]) return false; } return true; } int main() { assert(test(LLA{3, 10, 11, 23}, 4, LLA{4, 2, 5, 6, 11}, 5, LLA{4, 1, 6, 13, 63})); assert(test(LLA{0, 0, 0, 0}, 4, LLA{4, 2, 5}, 3, LLA{40, 20, 50})); assert(test(LLA{0}, 1, LLA{1}, 1, LLA{1})); assert(test(LLA{0, 1000000000000L}, 2, LLA{1, 1000000}, 2, LLA{1, 1000000})); return 0; } #else int main() { int n, m; scanf("%d %d", &n, &m); for(int i = 0; i < n; i++) { scanf("%lld", &k[i]); } for(int i = 0; i < m; i++) { scanf("%lld", &p[i]); } zap(n, m); for(int i = 0; i < m; i++) { printf("%lld\n", o[i]); } return 0; } #endif
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 | #include <cstdio> #include <cmath> #include <cassert> #include <string> #include <algorithm> #include <functional> //#define DEBUG #ifdef DEBUG #define D(x); x #else #define D(x); #endif #define LL long long #define LLA (long long []) using namespace std; LL k[200002]; // n LL p[200002]; // m LL o[200002]; void print_input(int n, int m) { for(int i = 0; i < n; i++) { printf("%lld ", k[i]); } printf("\n"); for(int i = 0; i < m; i++) { printf("%lld ", p[i]); } printf("\n"); } void print_output(int m) { for(int i = 0; i < m; i++) { printf("%lld ", o[i]); } printf("\n"); } void zap(int n, int m) { D(printf("---\nZAP for arrays (%d, %d):\n", n, m);); D(print_input(n, m);); for(int j = 0; j < m; j++) { o[j] = 0L; LL time = p[j]; LL prevk = 0L; LL prev_wait = 0L; D(printf("--- p[%d] = %lld ---\n", j, p[j]);); for(int i = 0; i < n; i++) { LL diff = k[i] - (prevk + prev_wait); LL wait = 0; if(time > diff) wait = time - diff; o[j] += wait; D(printf("k[%d] comes @%lld, has %lld buffer and waits %lld (total %lld)\n", i, k[i], diff, wait, o[j]);); prevk = k[i]; prev_wait = wait; } } D(print_output(m);); } #ifdef DEBUG bool test(LL A[], int a, LL B[], int b, LL C[]) { std::copy(A, A + a, k); std::copy(B, B + b, p); zap(a, b); for(int i = 0; i < b; i++) { if(o[i] != C[i]) return false; } return true; } int main() { assert(test(LLA{3, 10, 11, 23}, 4, LLA{4, 2, 5, 6, 11}, 5, LLA{4, 1, 6, 13, 63})); assert(test(LLA{0, 0, 0, 0}, 4, LLA{4, 2, 5}, 3, LLA{40, 20, 50})); assert(test(LLA{0}, 1, LLA{1}, 1, LLA{1})); assert(test(LLA{0, 1000000000000L}, 2, LLA{1, 1000000}, 2, LLA{1, 1000000})); return 0; } #else int main() { int n, m; scanf("%d %d", &n, &m); for(int i = 0; i < n; i++) { scanf("%lld", &k[i]); } for(int i = 0; i < m; i++) { scanf("%lld", &p[i]); } zap(n, m); for(int i = 0; i < m; i++) { printf("%lld\n", o[i]); } return 0; } #endif |