Kyselyt

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
 
using namespace std;
 
long long st[4*200000];
int mt[4*200000];
int bs[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];
		bs[v] = 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]);
		bs[v] = (mt[v*2] < mt[v*2+1]) ? bs[v*2+1] : bs[v*2];
	}
}
 
long long 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);
}
 
pair<int, int> query_mt(int v, int tl, int tr, int l, int r) {
	if (l > r) 
		return make_pair(0, 0);
	if (l == tl && r == tr) {
		return make_pair(mt[v], bs[v]);
	}
	int tm = (tl + tr) / 2;
	auto res1 = query_mt(v*2, tl, tm, l, min(r, tm));
	auto res2 = query_mt(v*2+1, tm+1, tr, max(l, tm+1), r);
	return res1.first < res2.first ? res2 : res1;
}
 
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);
	for (int i = 0; i < n; ++i) {
		cin >> v[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;
		long long o = 0;
		while (a < b) {
			auto qq = query_mt(1, 0, n - 1, a, b);
			if (qq.second == b) {
				--b;
				continue;
			}
			auto thesum = query_st(1, 0, n - 1, qq.second + 1, b);
			o += (long long)(b - qq.second) * (long long)qq.first - thesum;
			b = qq.second - 1;
		}
		cout << o << endl;
	}
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 3

Verdict: ACCEPTED