#include <map> #include <utility> #include <cstdio> typedef long long int LL; int main(void) { std::map<int, std::pair<int, LL> > a; std::map<int, std::pair<int, LL> >::iterator it; int n, m, x; LL d, b, c, w, y; scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%d", &x); it = a.find(x); if (it != a.end()) { ++it->second.first; } else { a.insert(std::pair<int, std::pair<int, LL> >(x, std::pair<int, LL>(0, 0))); } } c = 0; for (int i = 0; i < m; ++i) { scanf("%lld%lld", &d, &b); w = 0; y = d - c; for (it = a.begin(); it != a.end(); ++it) { it->second.second += it->first; if (it->second.second > b) { w += (it->second.second - b)*y; it->second.second = b; } } printf("%lld\n", w); c = d; } 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 | #include <map> #include <utility> #include <cstdio> typedef long long int LL; int main(void) { std::map<int, std::pair<int, LL> > a; std::map<int, std::pair<int, LL> >::iterator it; int n, m, x; LL d, b, c, w, y; scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%d", &x); it = a.find(x); if (it != a.end()) { ++it->second.first; } else { a.insert(std::pair<int, std::pair<int, LL> >(x, std::pair<int, LL>(0, 0))); } } c = 0; for (int i = 0; i < m; ++i) { scanf("%lld%lld", &d, &b); w = 0; y = d - c; for (it = a.begin(); it != a.end(); ++it) { it->second.second += it->first; if (it->second.second > b) { w += (it->second.second - b)*y; it->second.second = b; } } printf("%lld\n", w); c = d; } return 0; } |