Submission #541321

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
541321	2022-03-23T04:52:55 Z	Fidan	Addk (eJOI21_addk)	C++17	92 / 100	187 ms	6584 KB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll N = 1000'010;
ll sumpre(ll x, ll y, vector<ll> &pre, vector<ll> &dp){
	return pre[y]-pre[x-1]-(x-1)*(dp[y]-dp[x-1]);
}
ll sumsuf(ll x, ll y, vector<ll> &pre, vector<ll> &dp){
	return (y-x+2)*(dp[y]-dp[x-1])-sumpre(x, y, pre, dp);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	ll n, k, i;
	cin>>n>>k;
	
	vector<ll> a(n+1, 0);
	for(i=1; i<=n; i++){
		cin>>a[i];
	}
	
	vector<ll> pre(n+1, 0);
	vector<ll> dp(n+1, 0);
	
	for(i=1; i<=n; i++){
		pre[i]=pre[i-1]+i*a[i];
		dp[i]=dp[i-1]+a[i];
	}
	
	ll q;
	cin>>q;
	while(q--){
		ll t;
		cin>>t;
		if(t==1){
			for(i=0; i<k; i++){
				ll x1;
				cin>>x1;
			}
		}
		else {
			ll l, r, m, k, s=0, b;
			cin>>l>>r>>m;
			k=r-l+1;
			if(k>=2*m){
				s=sumpre(l, l+m-1, pre, dp)+m*(dp[r-m]-dp[l+m-1])+sumsuf(r-m+1, r, pre, dp);
			}
			else {
				b=k-m+1;
				s=sumpre(l, l+b-1, pre, dp)+b*(dp[r-b]-dp[l+b-1])+sumsuf(r-b+1, r, pre, dp);
			}
			cout<<s<<endl;
		}
	}
	return 0;
}

Subtask #1

36.0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	3 ms	340 KB	Output is correct
4	Correct	5 ms	468 KB	Output is correct
5	Correct	7 ms	456 KB	Output is correct
6	Correct	8 ms	596 KB	Output is correct
7	Correct	10 ms	588 KB	Output is correct
8	Correct	12 ms	768 KB	Output is correct
9	Correct	16 ms	840 KB	Output is correct

Subtask #2

56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	1108 KB	Output is correct
2	Correct	51 ms	2108 KB	Output is correct
3	Correct	66 ms	2796 KB	Output is correct
4	Correct	115 ms	4708 KB	Output is correct
5	Correct	163 ms	6584 KB	Output is correct
6	Correct	144 ms	6348 KB	Output is correct
7	Correct	187 ms	6336 KB	Output is correct

Subtask #3

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	88 ms	1996 KB	Output isn't correct
2	Halted	0 ms	0 KB	-