Task: | Kyselyt |
Sender: | PallomerenPiikki |
Submission time: | 2020-10-18 12:04:09 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 34 |
#3 | ACCEPTED | 54 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.96 s | 2, 3 | details |
#3 | ACCEPTED | 0.69 s | 3 | details |
#4 | ACCEPTED | 0.84 s | 3 | details |
#5 | ACCEPTED | 0.53 s | 3 | details |
Code
#include <bits/stdc++.h>using namespace std;#define int long longconst int NLOG = 18;const int NMAX = 1 << NLOG;int n;int arr[NMAX];int psum[NMAX];int dp[2*NMAX][NLOG+1];int dpmax[2*NMAX][NLOG+1];int nbigger[NMAX];int cost(int lvl, int a, int b) {return lvl*(b-a+1) - (psum[b+1]-psum[a]);}int step(int& lvl, int& i, int b) {if (lvl == arr[i]) {int l = 1;while (l < NLOG && i+(1<<l) <= b) l++;l--;int ans = dp[i][l];lvl = dpmax[i][l];i += 1<<l;lvl = max(lvl, arr[i]);return ans;}int j = nbigger[i];int ans = cost(lvl, i, min(b, j-1));i = j;lvl = max(lvl, arr[i]);return ans;}int query_step(int a, int b, int lvl) {b = min(b, n);lvl = max(lvl, arr[a]);int ans = 0;for (int i=a; i<=b;) {ans += step(lvl, i, b);}return ans;}int query(int a, int b) {return query_step(a, b, arr[a]);}void init() {for (int i=0; i<n; i++) {psum[i+1] = psum[i] + arr[i];}vector<int> s;s.push_back(n);for (int i=n-1; i>=0; i--) {while (arr[i] > arr[s.back()]) s.pop_back();nbigger[i] = s.back();s.push_back(i);}for (int i=0; i<n; i++) {dp[i][0] = 0;dpmax[i][0] = arr[i];}for (int l=1; l<NLOG; l++) {for (int i=0; i<n; i++) {int i2 = min(n, i + (1<<(l-1)));dpmax[i][l] = max(dpmax[i][l-1], dpmax[i2][l-1]);int lvl = dpmax[i][l-1];int i3 = min(n, i2 + (i2-i));dp[i][l] = dp[i][l-1] + query_step(i2, i3-1, lvl);}}}signed main() {ios::sync_with_stdio(0);int q;cin >> n >> q;for (int i=0; i<n; i++) {cin >> arr[i];}arr[n] = 1 + *max_element(arr, arr+n);init();for (int i=0; i<q; i++) {int a, b;cin >> a >> b, a--, b--;if (a > b) swap(a, b);cout << query(a, 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: ACCEPTED
input |
---|
200000 200000 818377786 934884634 816080381 ... |
correct output |
---|
86877225712611 94684086875470 92703793485296 38149694892093 61948503092286 ... |
user output |
---|
86877225712611 94684086875470 92703793485296 38149694892093 61948503092286 ... Truncated |
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 ... Truncated |
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 ... Truncated |