Task: | Kyselyt |
Sender: | Metabolix |
Submission time: | 2020-10-17 11:35:17 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
#3 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.01 s | 1, 2, 3 | details |
#2 | WRONG ANSWER | 0.79 s | 2, 3 | details |
#3 | WRONG ANSWER | 0.82 s | 3 | details |
#4 | TIME LIMIT EXCEEDED | -- | 3 | details |
#5 | WRONG ANSWER | 0.65 s | 3 | details |
Compiler report
input/code.cpp: In function 'long int tulos(int, int)': input/code.cpp:37:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses] long key = ((long)a << MAXPOW + b); ^
Code
#include <bits/stdc++.h>#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);}std::unordered_map<long, long> cache;long tulos(int a, int b) {long key = ((long)a << MAXPOW + b);auto iter = cache.find(key);if (iter != cache.end()) {return iter->second;}auto m = max_valilla(a, b);if (t[a] == m.first) {return cache[key] = (b - a) * (long) m.first - summa(a, b);}int p = m.second;return cache[key] = 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: WRONG ANSWER
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: WRONG ANSWER
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: WRONG ANSWER
input |
---|
200000 200000 818377786 934884634 816080381 ... |
correct output |
---|
86877225712611 94684086875470 92703793485296 38149694892093 61948503092286 ... |
user output |
---|
86877225712611 94684086875470 91361548688063 38149694892093 61953910764937 ... Truncated |
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 |
---|
15920862903 3193483321 18874982071 4846348926 3970697055 ... Truncated |