CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Kyselyt
Sender:Metabolix
Submission time:2020-10-17 14:15:31
Language:C++17
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED34
#3ACCEPTED54
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.52 s2, 3details
#3ACCEPTED0.56 s3details
#4ACCEPTED0.55 s3details
#5ACCEPTED0.54 s3details

Code

#include <bits/stdc++.h>

#define MAXPOW 19
#define MAX 200002

int n, q;
int luku[MAX];
int minimitaso[MAX];
long hinta_alusta[MAX];
long hinta_loppuun[MAX];
int max[MAX][MAXPOW];
int maxpos[MAX][MAXPOW];

std::pair<int, int> max_valilla(int a, int b) {
	int l = b - a;
	int pow = __builtin_ctz(l & -l);
	int p = a + (1 << pow);
	if (p != b) {
		auto r = max_valilla(p, b);
		if (r.first > max[p-1][pow]) {
			return r;
		}
	}
	return {max[p-1][pow], maxpos[p-1][pow]};
}

int main() {
	std::cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		std::cin >> luku[i];

		// Lasketaan taulukoihin tietoa lukuvälien maksimiluvuista.
		max[i][0] = luku[i];
		maxpos[i][0] = i;
		for (int p = 1; p < MAXPOW; ++p) {
			int j = i - (1 << (p - 1));
			max[i][p] = max[i][p-1];
			maxpos[i][p] = maxpos[i][p-1];
			if (j >= 0 && max[j][p-1] >= max[i][p-1]) {
				maxpos[i][p] = maxpos[j][p-1];
				max[i][p] = max[j][p-1];
			}
		}

		// Hinta alusta tähän on vähintään sama kuin aiemmin.
		hinta_alusta[i] = hinta_alusta[i-1];

		// Jos luku on alle minimitason, sen kasvatus maksaa.
		if (luku[i] < minimitaso[i-1]) {
			minimitaso[i] = minimitaso[i-1];
			hinta_alusta[i] += minimitaso[i] - luku[i];
		} else {
			minimitaso[i] = luku[i];
		}
	}

	// Lopusta alkuun.
	std::map<int, int> luvut;
	for (int i = n; i > 0; --i) {
		// Hinta tästä loppuun on vähintään sama kuin tätä seuraavasta.
		hinta_loppuun[i] = hinta_loppuun[i+1];
		luvut[luku[i]] += 1;

		// Kaikki liian pienet luvut pitää nostaa nykyiseen lukuun asti.
		while (luvut.begin()->first < luku[i]) {
			int pieni_luku = luvut.begin()->first, montako = luvut.begin()->second;
			luvut.erase(luvut.begin());
			luvut[luku[i]] += montako;
			hinta_loppuun[i] += montako * (long) (luku[i] - pieni_luku);
		}
	}

	for (int i = 0; i < q; ++i) {
		int a, b;
		std::cin >> a >> b;

		// Haetaan maksimin paikka.
		int c = max_valilla(a, b+1).second;
		// Alkupuolen hinta saadaan loppuhintojen erona.
		long ac = hinta_loppuun[a] - hinta_loppuun[c];
		// Loppupuolen hinta saadaan alkuhintojen erona, ja lisäksi pitää huomioida, että minimitaso voi olla eri kuin nyt löydetty huippu.
		long cb = hinta_alusta[b] - hinta_alusta[c] + (b - c) * (long) (luku[c] - minimitaso[c]);
		std::cout << (ac + cb) << '\n';
	}
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100 100
70 8 72 88 42 78 85 41 23 36 6...

correct output
99
0
922
2579
1892
...

user output
99
0
922
2579
1892
...

Test 2

Group: 2, 3

Verdict: ACCEPTED

input
200000 200000
98 99 29 92 29 81 100 52 89 80...

correct output
1497732
2810356
9532632
6655773
5403513
...

user output
1497732
2810356
9532632
6655773
5403513
...

Test 3

Group: 3

Verdict: ACCEPTED

input
200000 200000
818377786 934884634 816080381 ...

correct output
86877225712611
94684086875470
92703793485296
38149694892093
61948503092286
...

user output
86877225712611
94684086875470
92703793485296
38149694892093
61948503092286
...

Test 4

Group: 3

Verdict: ACCEPTED

input
200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 5

Group: 3

Verdict: ACCEPTED

input
200000 200000
200000 199999 199998 199997 19...

correct output
15920862903
3193483321
18874982071
4846348926
3970697055
...

user output
15920862903
3193483321
18874982071
4846348926
3970697055
...