Kyselyt

input/code.cpp: In function 'int main()':
input/code.cpp:69:10: warning: unused variable 'lb' [-Wunused-variable]
      int lb =bi.first; // INCLUSIVE BOTH
          ^~

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define M 1000000007

using namespace std;

ll x[202020];
ll ans[202020], xs[202020];

vector<pair<int,int>> bq[202020];

// X, Korkeus, Summa, pituus(helppouden takia)
set<tuple<ll, ll, ll, ll>> st;

ll ts(int a, int b) {
	return xs[b]-xs[a-1];
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio();
	int n, q;
	cin >> n >> q;
	for(int i=0; i<n; i++) {
		cin >> x[i];
		xs[i] = xs[i-1]+x[i];
	}

	for(int i=0; i<q; i++) {
		int a, b;
		cin >> a >> b;
		b--;
		a--;
		bq[a].push_back(make_pair(b, i));
	}
	
	ll sum = 0;
	ll ht = 0;
	for(int i=n-1; i>=0; i--) {
		// updt set
		ht = x[i];
		auto u = make_tuple(i,ht,0,1);
		if(!st.empty())
			get<2>(u) = get<2>(*st.begin());
		while(st.begin() != st.end() && get<1>(*st.begin()) <= ht)  {
			sum += get<3>(*st.begin())*(ht-get<1>(*st.begin()));
			get<2>(u) += get<3>(*st.begin())*(ht-get<1>(*st.begin()));
			get<3>(u) += get<3>(*st.begin());
			st.erase(st.begin());
		}
		st.insert(u);

		// handle bq
		for(auto bi:bq[i]) {
			ll bans = sum;

			auto it = st.upper_bound({bi.first,0,0,0});

			if(it != st.end()) {
				bans -= get<2>(*it);
			}
			if(it != st.begin()) {
				it--;

				auto ed = *it;
				if(get<0>(ed)+get<3>(ed)-1 > bi.first) {
					int lb =bi.first; // INCLUSIVE BOTH
					int rb = get<0>(ed)+get<3>(ed)-1;
					bans -= (rb-bi.first)*get<1>(ed)-ts(bi.first+1, rb);
				}
			}

			ans[bi.second] = bans;
		}
	}

	for(int i=0; i<q; i++)
		cout << ans[i] << "\n";
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: WRONG ANSWER

Test 4

Group: 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: ACCEPTED