This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "peru.h"
#include <bits/stdc++.h>
#define X first
#define Y second
typedef long long llint;
using namespace std;
const int mod = 1e9+7;
const int maxn = 25e5+10;
struct node {
int ind;
int first;
llint second;
node(int ind, int first, llint second) {
this->ind = ind;
this->first = first;
this->second = second;
}
pair<int, llint> p() {return {first, second};}
};
llint dp[maxn];
deque< node > s;
stack< llint > l, r;
int mul(int a, int b) {
llint out = (llint)a * b;
return out % mod;
}
void rebuild() {
while (!l.empty()) l.pop();
while (!r.empty()) r.pop();
deque< node > c = s;
int kol = c.size() / 2;
stack< llint > t;
for (int i = 0; i < kol; i++) {
t.push(c.front().X + c.front().Y);
c.pop_front();
}
while (!t.empty()) {
if (l.empty() || l.top() >= t.top()) l.push(t.top());
t.pop();
}
while (!c.empty()) {
t.push(c.back().X + c.back().Y);
c.pop_back();
}
while (!t.empty()) {
if (r.empty() || r.top() >= t.top()) r.push(t.top());
t.pop();
}
}
void pop_right() {
//printf("poppin\n");
llint x = s.back().X + s.back().Y;
s.pop_back();
if (r.empty()) rebuild();
else if (r.top() == x) r.pop();
}
void pop_left(int y) {
node tr = s.front();
int ind = tr.ind;
llint x = tr.X + tr.Y;
s.pop_front();
if (l.empty()) rebuild();
else if (l.top() == x) l.pop();
if (y < ind) {
tr.Y = dp[y + 1];
if (l.empty() || l.top() >= tr.X + tr.Y) l.push(tr.X + tr.Y);
s.push_front(tr);
}
}
bool cmp(pair<int, llint> a, pair<int, llint> b) {
if (a.X == b.X) return a.Y < b.Y;
else return a.X > b.X;
}
void push_right(int h, llint val, int ind) {
while (!s.empty() && cmp({h, val}, s.back().p())) {
val = min(val, s.back().Y);
pop_right();
}
s.push_back(node(ind, h, val));
if (r.empty() || r.top() >= h + val) r.push(h + val);
}
void debug() {
printf("deque: ");
for (auto iter : s) printf("(%d %lld, %d) ", iter.X, iter.Y, iter.ind);
printf("\n");
}
llint get_min() {
llint out = 1LL << 60;
if (!l.empty()) out = min(out, l.top());
if (!r.empty()) out = min(out, r.top());
return out;
}
int solve(int n, int k, int* v){
/*push_right(v[0], 0, 0);
for (int i = 1; i <= n; i++) {
dp[i] = get_min();
//debug();
//printf("dp %d: %lld\n", i, dp[i]);
if (i < n) push_right(v[i], dp[i], i);
if (i >= k) pop_left(i - k);
}
*/
int sol = 0;
int pot = 1;
for (int i = n; i >= 0; i--) {
sol += mul(dp[i] % mod, pot), sol %= mod;
pot = mul(pot, 23);
}
return sol;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |