結果
問題 |
No.1012 荷物収集
|
ユーザー |
|
提出日時 | 2020-07-07 09:48:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 144 ms / 2,000 ms |
コード長 | 1,097 bytes |
コンパイル時間 | 3,322 ms |
コンパイル使用メモリ | 205,300 KB |
最終ジャッジ日時 | 2025-01-11 16:39:41 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<vector<int>> v; for (int i = 0; i < n; i++) { int x, w; cin >> x >> w; v.push_back({x, w, 0}); } v.push_back({0, 0, 0}); v.push_back({(int) 1e9 + 1, 0, 0}); for (int i = 0; i < q; i++) { int x; cin >> x; v.push_back({x, i, 1}); } sort(v.begin(), v.end()); vector<long long> pref((int) v.size()); vector<long long> ans(q); long long w_tot = 0; for (int i = 1; i < (int) v.size(); i++) { pref[i] = pref[i - 1] + w_tot * (v[i][0] - v[i - 1][0]); if (v[i][2] == 0) { w_tot += v[i][1]; } else { ans[v[i][1]] += pref[i]; } } vector<long long> suff((int) v.size()); w_tot = 0; for (int i = (int) v.size() - 2; i >= 1; i--) { suff[i] = suff[i + 1] + w_tot * (v[i + 1][0] - v[i][0]); if (v[i][2] == 0) { w_tot += v[i][1]; } else { ans[v[i][1]] += suff[i]; } } for (auto& p : ans) { cout << p << '\n'; } return 0; }