2 条题解
-
0
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef struct Function_tag { ll k; ll b; Function_tag(){} Function_tag(ll k_, ll b_){ k = k_; b = b_; } inline ull calc(int x){ return (ull)k * x + b; } } Function; int cnt[300007], a[300007], b[300007], c[300007], d[300007], e[300007]; ll l[300007]; Function f[300007], g[300007], h[300007]; Function operator +(const Function a, const Function b){ return Function(a.k + b.k, a.b + b.b); } Function operator +=(Function &a, const Function b){ return a = a + b; } Function operator -(const Function a, const Function b){ return Function(a.k - b.k, a.b - b.b); } Function operator -=(Function &a, const Function b){ return a = a - b; } inline int read(){ int ans = 0; char ch = getchar(); while (ch < '0' || ch > '9'){ ch = getchar(); } while (ch >= '0' && ch <= '9'){ ans = ans * 10 + (ch ^ 48); ch = getchar(); } return ans; } int main(){ int n = read(), m = read(), q = read(), x = 0; l[++x] = 1; for (register int i = 1; i <= n; i++){ int p = read(); cnt[p]++; } for (register int i = 1; i <= m; i++){ a[i] = read(); } for (register int i = 1; i <= m; i++){ b[i] = read(); } for (register int i = 1; i <= m; i++){ c[i] = read(); } for (register int i = 1; i <= m; i++){ d[i] = read(); } for (register int i = 1; i <= m; i++){ e[i] = read(); } for (register int i = 1; i <= m; i++){ if (cnt[i] > 0){ ll pos; f[i].k = d[i]; f[i].b = (ll)a[i] * cnt[i]; g[i].k = e[i]; g[i].b = b[i] + (ll)c[i] * cnt[i]; pos = (f[i].b - g[i].b) / (g[i].k - f[i].k) + 1; if (pos >= 1) l[++x] = pos; } } sort(l + 1, l + x + 1); x = unique(l + 1, l + x + 1) - l - 1; for (register int i = 1; i <= m; i++){ if (cnt[i] > 0){ ll pos1 = (f[i].b - g[i].b) / (g[i].k - f[i].k) + 1; if (pos1 <= 0){ h[1] += f[i]; } else { int pos2 = lower_bound(l + 1, l + x + 1, pos1) - l; h[1] += g[i]; h[pos2] -= g[i]; h[pos2] += f[i]; } } } for (register int i = 1; i <= x; i++){ h[i] += h[i - 1]; } for (register int i = 1; i <= q; i++){ int k = read(); cout << h[upper_bound(l + 1, l + x + 1, k) - l - 1].calc(k) << endl; } return 0; }
信息
- ID
- 279
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 50
- 已通过
- 17
- 上传者