Kyselyt

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int st[4*200000];
int mt[4*200000];

void build_st(int a[], int v, int tl, int tr) {
	if (tl == tr) {
		st[v] = a[tl];
	} else {
		int tm = (tl + tr) / 2;
		build_st(a, v*2, tl, tm);
		build_st(a, v*2+1, tm+1, tr);
		st[v] = st[v*2] + st[v*2+1];
	}
}

void build_mt(int a[], int v, int tl, int tr) {
	if (tl == tr) {
		mt[v] = a[tl];
	} else {
		int tm = (tl + tr) / 2;
		build_mt(a, v*2, tl, tm);
		build_mt(a, v*2+1, tm+1, tr);
		mt[v] = max(mt[v*2], mt[v*2+1]);
	}
}

int query_st(int v, int tl, int tr, int l, int r) {
	if (l > r) 
		return 0;
	if (l == tl && r == tr) {
		return st[v];
	}
	int tm = (tl + tr) / 2;
	return query_st(v*2, tl, tm, l, min(r, tm))
		   + query_st(v*2+1, tm+1, tr, max(l, tm+1), r);
}

int query_mt(int v, int tl, int tr, int l, int r) {
	if (l > r) 
		return 0;
	if (l == tl && r == tr) {
		return mt[v];
	}
	int tm = (tl + tr) / 2;
	return max(query_mt(v*2, tl, tm, l, min(r, tm)),
				query_mt(v*2+1, tm+1, tr, max(l, tm+1), r));
}

template <typename T>
int ops(T l, T r) {
	if (l == r) return 0;
	auto m = max_element(l, r);
	int cnt = 0;
	for (auto it = m; it < r; ++it) {
		cnt += *m - *it;
	}
	return cnt + ops(l, m);
}

int main()
{
	int n, q;
	cin >> n >> q;
	vector<int> v(n);
	unordered_map<int, int> mp;
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
		mp[v[i]] = i;
	}
	build_st(v.data(), 1, 0, n - 1);
	build_mt(v.data(), 1, 0, n - 1);
	for (int i = 0; i < q; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		int o = 0;
		while (a < b) {
			//cout << a << " " << b << endl;
			auto foundmax = query_mt(1, 0, n - 1, a, b);
			//cout << foundmax << endl;
			auto maxind = mp[foundmax];
			//cout << maxind << endl;
			if (maxind == b) {
				--b;
				continue;
			}
			auto thesum = query_st(1, 0, n - 1, maxind + 1, b);
			//cout << thesum << endl;
			o += (b - maxind) * foundmax - thesum;
			b = maxind - 1;
		}
		cout << o << endl;
		//cout << ops(v.begin() + a - 1, v.begin() + b) << endl;
	}
}

Test 1

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 3

Verdict: WRONG ANSWER