結果
問題 | No.1012 荷物収集 |
ユーザー | Sumitacchan |
提出日時 | 2020-03-20 21:41:32 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 190 ms / 2,000 ms |
コード長 | 3,406 bytes |
コンパイル時間 | 2,052 ms |
コンパイル使用メモリ | 172,564 KB |
実行使用メモリ | 8,652 KB |
最終ジャッジ日時 | 2023-08-21 15:55:29 |
合計ジャッジ時間 | 9,125 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 177 ms
8,484 KB |
testcase_05 | AC | 178 ms
8,564 KB |
testcase_06 | AC | 179 ms
8,648 KB |
testcase_07 | AC | 178 ms
8,652 KB |
testcase_08 | AC | 173 ms
8,460 KB |
testcase_09 | AC | 179 ms
8,636 KB |
testcase_10 | AC | 174 ms
8,460 KB |
testcase_11 | AC | 176 ms
8,568 KB |
testcase_12 | AC | 177 ms
8,500 KB |
testcase_13 | AC | 180 ms
8,612 KB |
testcase_14 | AC | 2 ms
4,376 KB |
testcase_15 | AC | 3 ms
4,380 KB |
testcase_16 | AC | 2 ms
4,376 KB |
testcase_17 | AC | 3 ms
4,376 KB |
testcase_18 | AC | 3 ms
4,376 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 2 ms
4,376 KB |
testcase_21 | AC | 2 ms
4,376 KB |
testcase_22 | AC | 3 ms
4,380 KB |
testcase_23 | AC | 2 ms
4,376 KB |
testcase_24 | AC | 142 ms
6,308 KB |
testcase_25 | AC | 177 ms
7,812 KB |
testcase_26 | AC | 66 ms
6,452 KB |
testcase_27 | AC | 15 ms
4,380 KB |
testcase_28 | AC | 164 ms
7,944 KB |
testcase_29 | AC | 50 ms
6,868 KB |
testcase_30 | AC | 161 ms
8,068 KB |
testcase_31 | AC | 104 ms
4,376 KB |
testcase_32 | AC | 65 ms
4,648 KB |
testcase_33 | AC | 114 ms
5,124 KB |
testcase_34 | AC | 132 ms
4,812 KB |
testcase_35 | AC | 139 ms
7,236 KB |
testcase_36 | AC | 133 ms
4,760 KB |
testcase_37 | AC | 49 ms
6,808 KB |
testcase_38 | AC | 145 ms
6,520 KB |
testcase_39 | AC | 58 ms
4,856 KB |
testcase_40 | AC | 76 ms
4,932 KB |
testcase_41 | AC | 190 ms
8,304 KB |
testcase_42 | AC | 96 ms
5,612 KB |
testcase_43 | AC | 115 ms
6,464 KB |
testcase_44 | AC | 1 ms
4,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; /*#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/ struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; #define FOR(i, begin, end) for(int i=(begin);i<(end);i++) #define REP(i, n) FOR(i,0,n) #define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--) #define IREP(i, n) IFOR(i,0,n) #define Sort(v) sort(v.begin(), v.end()) #define Reverse(v) reverse(v.begin(), v.end()) #define all(v) v.begin(),v.end() #define SZ(v) ((int)v.size()) #define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x)) #define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x)) #define Max(a, b) a = max(a, b) #define Min(a, b) a = min(a, b) #define bit(n) (1LL<<(n)) #define bit_exist(x, n) ((x >> n) & 1) #define debug(x) cout << #x << "=" << x << endl; #define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; } #define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} } #define Return(ans) { cout << (ans) << endl; return 0; } #define pb push_back #define f first #define s second #define int long long #define INF 1000000000000000000 template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; } template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; } template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; } template<typename T> void Out(T x) { cout << x << endl; } template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); } using vec = vector<int>; using mat = vector<vec>; using Pii = pair<int, int>; using PiP = pair<int, Pii>; using PPi = pair<Pii, int>; using bools = vector<bool>; using pairs = vector<Pii>; //int dx[4] = {1,0,-1,0}; //int dy[4] = {0,1,0,-1}; //char d[4] = {'D','R','U','L'}; const int mod = 1000000007; //const int mod = 998244353; //#define Add(x, y) x = (x + (y)) % mod //#define Mult(x, y) x = (x * (y)) % mod signed main(){ int N, Q; cin >> N >> Q; vec x(N), w(N); vec v; REP(i, N){ cin >> x[i] >> w[i]; v.pb(x[i]); } Sort(v); vec s_xw(N + 1), s_w(N + 1); REP(i, N){ int i0 = Lower_bound(v, x[i]); s_xw[i0 + 1] = x[i] * w[i]; s_w[i0 + 1] = w[i]; } REP(i, N){ s_xw[i + 1] += s_xw[i]; s_w[i + 1] += s_w[i]; } vec X(Q); cin >> X; vec ans(Q); REP(q, Q){ int i = Lower_bound(v, X[q]); int ans = 0; ans += s_w[i] * X[q] - s_xw[i]; ans += (s_xw[N] - s_xw[i]) - (s_w[N] - s_w[i]) * X[q]; Out(ans); } return 0; }