// Esti <3
//\
šťastia pre nás :)
// you're already the best
// _
// ^ ^ //
// >(O_O)<___//
// \ __ __ \
// \\ \\ \\\\
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3","unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
using ll = long long;
#define int long long
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll inf = 1e18;
const ll mod = 1e9+7;//998244853;
// \
\
:smiling_face_with_3_hearts: :smiling_face_with_3_hearts: :smiling_face_with_3_hearts:
//vidime sa veľmi skoro, moje slnko
const int sz = 1<<22;
struct node {
int ans=inf, mina=0;
bool full=1;
int32_t maxb=0, minb=0;
};
node t[2*sz];
int32_t lazy[2*sz];
void merge(node&ret, node a, node b) {
ret.ans = min(a.ans, b.ans);
ret.full = (a.full && b.full) && (a.maxb == b.maxb);
ret.mina = min(a.mina, b.mina);
ret.maxb = max(a.maxb, b.maxb);
ret.minb = min(a.minb, b.minb);
if (ret.full) ret.ans=min(ret.ans, ret.maxb + ret.mina);
}
int32_t x;
void push(int v) {
x = lazy[v];
lazy[v]=0;
if (2*v+2<2*sz) {
lazy[2*v+1] = max(lazy[2*v+1],x);
lazy[2*v+2] = max(lazy[2*v+2],x);
}
t[v].minb = t[v].maxb = x;
t[v].ans = t[v].mina + x;
t[v].full = 1;
}
void Set(int i, int x) {
t[sz-1+i].mina = x;
t[sz-1+i].ans = x + t[sz-1+i].maxb;
int v = (sz+i-2)>>1;
while (v > 0) {
merge(t[v],t[2*v+1],t[2*v+2]);
v = (v-1)>>1;
}
merge(t[0],t[1],t[2]);
}
void upd(int v, int l, int r, int lx, int rx, int x) {
if (lazy[v]) push(v);
if (t[v].minb >= x) return;
if (rx<=l || r<=lx) return;
if (lx<=l && r<=rx) {
if (t[v].maxb <= x) {
lazy[v] = x;
push(v);
return;
}
assert(r-l > 1);
}
int m=(l+r)>>1;
upd(2*v+1,l,m,lx,rx,x);
upd(2*v+2,m,r,lx,rx,x);
merge(t[v],t[2*v+1],t[2*v+2]);
}
void upd(int l, int r, int x) {
upd(0,0,sz,l,r,x);
}
int query(int v, int l, int r, int lx, int rx) {
if (lazy[v]) push(v);
if (rx<=l || r<=lx) return inf;
if (lx<=l && r<=rx) return t[v].ans;
int m=(l+r)>>1;
int lq = query(2*v+1,l,m,lx,rx);
int rq = query(2*v+2,m,r,lx,rx);
return min(lq,rq);
}
int query(int l, int r) {
return query(0,0,sz,l,r);
}
int32_t solve(int32_t n, int32_t k, int32_t* a) {
if (n==1) return a[0]%mod;
Set(0,0);
vector<int> dp(n+1,inf);
dp[0]=0;
for (int i=1; i<=n; ++i) {
upd(0,i,a[i-1]);
int x = query(max(i-k,0ll),i);
dp[i] = x;
Set(i,x);
}
int ans=0, p=1;
for (int i=n; i; --i) {
dp[i]%=mod;
ans=(ans+p*dp[i])%mod;
p=(p*23)%mod;
}
return ans;
}
Compilation message
Compilation timeout while compiling peru
