2 条题解

  • 1
    @ 2023-11-19 21:39:56
    #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
    标签
    (无)
    递交数
    46
    已通过
    13
    上传者