Task: | Kyselyt |
Sender: | Metabolix |
Submission time: | 2020-10-17 11:31:41 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 46 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 34 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.73 s | 2, 3 | details |
#3 | TIME LIMIT EXCEEDED | -- | 3 | details |
#4 | TIME LIMIT EXCEEDED | -- | 3 | details |
#5 | WRONG ANSWER | 0.60 s | 3 | details |
Code
#include <iostream>#include <algorithm>#define MAXPOW 19int n, q;int t[200002];int lkm[200002][MAXPOW];long sum[200002][MAXPOW];int max[200002][MAXPOW];int maxpos[200002][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]};}long summa(int a, int b) {int l = b - a;int pow = __builtin_ctz(l & -l);int p = a + (1 << pow);if (p == b) {return sum[p-1][pow];}return sum[p-1][pow] + summa(p, b);}int tulos(int a, int b) {auto m = max_valilla(a, b);if (t[a] == m.first) {return (b - a) * m.first - summa(a, b);}int p = m.second;return tulos(a, p) + tulos(p, b);}int main() {std::cin >> n >> q;for (int i = 0; i < n; ++i) {std::cin >> t[i];lkm[i][0] = 1;sum[i][0] = t[i];max[i][0] = t[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];lkm[i][p] = lkm[i][p-1];sum[i][p] = sum[i][p-1];maxpos[i][p] = maxpos[i][p-1];if (j >= 0) {if (max[j][p-1] >= max[i][p-1]) {maxpos[i][p] = maxpos[j][p-1];max[i][p] = max[j][p-1];}lkm[i][p] += lkm[j][p-1];sum[i][p] += sum[j][p-1];}}}for (int i = 0; i < q; ++i) {int a, b;std::cin >> a >> b;std::cout << tulos(a - 1, b) << '\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 ... Truncated |
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 ... Truncated |
Test 3
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 818377786 934884634 816080381 ... |
correct output |
---|
86877225712611 94684086875470 92703793485296 38149694892093 61948503092286 ... |
user output |
---|
(empty) |
Test 4
Group: 3
Verdict: TIME LIMIT EXCEEDED
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 |
---|
(empty) |
Test 5
Group: 3
Verdict: WRONG ANSWER
input |
---|
200000 200000 200000 199999 199998 199997 19... |
correct output |
---|
15920862903 3193483321 18874982071 4846348926 3970697055 ... |
user output |
---|
-1259006281 -1101483975 1695112887 551381630 -324270241 ... Truncated |