#include <iostream> #include <cstdint> #include <algorithm> #include <vector> using IntVector = std::vector<uint64_t>; int search(const IntVector& vector, uint64_t value) { if (value < vector[0]) return -1; if (value >= vector[vector.size() - 1]) return vector.size() - 1; int left = 0; int right = vector.size() - 1; while (left < right) { int middle = (left + right) >> 1; if (value == vector[middle]) return middle; if (value < vector[middle]) { right = middle - 1; } else { left = middle + 1; } } return right; } int main() { uint64_t n, m; std::cin >> n >> m; std::vector<uint64_t> t; std::vector<uint64_t> sum; t.resize(n); sum.resize(n); uint64_t prev = 0; uint64_t actual = 0; for (uint64_t i = 0; i < n; ++i) { std::cin >> actual; t[i] = actual - prev; prev = actual; } std::sort(t.begin(), t.end()); uint64_t total = 0; for (uint64_t i = 0; i < n; ++i) { total += t[i]; sum[i] = total; } for (uint64_t i = 0; i < m; ++i) { std::cin >> actual; int index = search(t, actual); if (index >= 0) std::cout << (actual * ((uint64_t)index + 1) - sum[index]) << std::endl; else std::cout << "0" << std::endl; } 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 | #include <iostream> #include <cstdint> #include <algorithm> #include <vector> using IntVector = std::vector<uint64_t>; int search(const IntVector& vector, uint64_t value) { if (value < vector[0]) return -1; if (value >= vector[vector.size() - 1]) return vector.size() - 1; int left = 0; int right = vector.size() - 1; while (left < right) { int middle = (left + right) >> 1; if (value == vector[middle]) return middle; if (value < vector[middle]) { right = middle - 1; } else { left = middle + 1; } } return right; } int main() { uint64_t n, m; std::cin >> n >> m; std::vector<uint64_t> t; std::vector<uint64_t> sum; t.resize(n); sum.resize(n); uint64_t prev = 0; uint64_t actual = 0; for (uint64_t i = 0; i < n; ++i) { std::cin >> actual; t[i] = actual - prev; prev = actual; } std::sort(t.begin(), t.end()); uint64_t total = 0; for (uint64_t i = 0; i < n; ++i) { total += t[i]; sum[i] = total; } for (uint64_t i = 0; i < m; ++i) { std::cin >> actual; int index = search(t, actual); if (index >= 0) std::cout << (actual * ((uint64_t)index + 1) - sum[index]) << std::endl; else std::cout << "0" << std::endl; } return 0; } |