// What we thought was for all time was momentary
// Still alive, killing time at the cemetery, never quite buried
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
const int mod = 1e9 + 7, base = 23;
void upd(int& a, int b) { a = (a + b) % mod; }
int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return (a * 1ll * b) % mod; }
const int maxn = 2.5e6 + 5;
int p[maxn];
ll dp[maxn], s[maxn];
int root(int i) { return p[i] == i ? i : p[i] = root(p[i]); }
void merge(int i, int j)
{
i = root(i), j = root(j);
p[i] = j;
}
ll eval(int i)
{
return dp[i] + s[root(i)];
}
deque<int> dpq;
deque<int> mq;
int solve(int n, int k, int* S)
{
for (int i = 0; i < n; i++) s[i] = S[i], p[i] = i;
for (int i = 1; i <= n; i++) // ideme postavit prefix dlzky i
{
if (dpq.size() && dpq.front() == i - k - 1) dpq.pop_front();
if (mq.size() && mq.front() == i - k - 1) mq.pop_front();
while (mq.size() && s[mq.back()] < s[i - 1]) merge(mq.back(), i - 1), mq.pop_back();
mq.push_back(i - 1);
while (dpq.size() && eval(i - 1) < eval(dpq.back())) dpq.pop_back();
dpq.push_back(i - 1);
dp[i] = eval(dpq.front());
//cout << i << " : " << dp[i] << "\n";
}
int ans = 0, m = 1;
for (int i = n; i >= 1; i--) upd(ans, mul(dp[i], m)), m = mul(m, base);
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
