結果
問題 | No.1012 荷物収集 |
ユーザー |
|
提出日時 | 2020-03-20 21:43:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 1,354 bytes |
コンパイル時間 | 1,769 ms |
コンパイル使用メモリ | 175,884 KB |
実行使用メモリ | 8,336 KB |
最終ジャッジ日時 | 2024-12-15 05:05:58 |
合計ジャッジ時間 | 6,308 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> using namespace std::literals::string_literals; using i64 = std::int_fast64_t; using std::cout; using std::cerr; using std::endl; using std::cin; template<typename T> std::vector<T> make_v(size_t a){return std::vector<T>(a);} template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts){ return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } int main() { int n, q; scanf("%d%d", &n, &q); std::vector<i64> a(n), b(n), c(q); for(int i = 0; i < n; i++) scanf("%lld%lld", &a[i], &b[i]); for(int i = 0; i < q; i++) scanf("%lld", &c[i]); std::vector<std::pair<int, int>> A, B; for(int i = 0; i < n; i++) A.push_back({a[i], i}); for(int i = 0; i < q; i++) B.push_back({c[i], i}); sort(begin(A), end(A)); sort(begin(B), end(B)); int cnt = 0; i64 now = 0, L = 0, R = std::accumulate(begin(b), end(b), 0LL), last = 0; for(int i = 0; i < n; i++) now += a[i] * b[i]; std::vector<i64> ans(q); for(int i = 0; i < B.size(); i++) { int x = B[i].first; while(cnt < A.size() and A[cnt].first <= x) { int id = A[cnt++].second; i64 len = a[id] - last; now += len * L; now -= len * R; last = a[id]; L += b[id]; R -= b[id]; } i64 len = x - last; now += len * L; now -= len * R; last = x; ans[B[i].second] = now; } for(auto v: ans) printf("%lld\n", v); return 0; }