Submission #339690

---

Source Code Expand

#include <iostream>
#include <string>
 
unsigned long long S[200000] = {}, score[200000] = {}, work[200000] = {};
 
int main()
{
	int N, Q;
	std::cin >> N;
	for(int i=0; i<N; ++i)
		std::cin >> S[i];
	std::cin >> Q;
 
	work[N-1] = S[N-1];
	for(int i=N-2; i>0; --i){
		if(work[i+1] > S[i]){
			work[i] = S[i];
			score[i] = score[i+1] + (~i&1) * work[i+1];
		} else {
			work[i] = work[i+1];
			score[i] = score[i+1] + (~i&1) * S[i];
		}
	}
	std::cout << S[0] + work[1] + score[1] << std::endl;

	for(int j=0; j<Q; ++j){
		int P;
		unsigned int D;
		std::cin >> P >> D;
		S[P-1] -= D;
		if(S[P-1]<1) S[P-1] = 1;

		for(int i=P-1; i>0; --i){
			if(i==N-1){
				work[i] = S[N-1];
			} else if(work[i+1] > S[i]){
				work[i] = S[i];
				score[i] = score[i+1] + (~i&1) * work[i+1];
			} else {
				work[i] = work[i+1];
				score[i] = score[i+1] + (~i&1) * S[i];
			}
		}
		std::cout << S[0] + work[1] + score[1] << std::endl;
	}
 
	return 0;
}

Submission Info

Judge Result