| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 596498 | Deepesson | Peru (RMI20_peru) | C++17 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#define MAX 2500005
int solve(int n, int k, int* v);
using ll = long long;
typedef std::pair<int,int> pii;
ll inf = 1LL<<60LL;
ll dp[MAX];
int N,K;
ll MOD = 1e9+7;
ll expo[MAX];
ll gera_hash(void){
ll hash = 0;
ll x = 1;
for(int i=N-1;i!=-1;--i){
hash = (hash + ((dp[i]%MOD)*x))%MOD;
x = (x*23LL)%MOD;
}
return hash;
}
ll t[MAX*2];
ll d[MAX*2];
ll h = sizeof(ll) * 8 - __builtin_clz(MAX);
void update(int p, const ll value) {
for (t[p += MAX] = value; p >>= 1; ) t[p] = std::min(t[p<<1], t[p<<1|1]);
}
void apply(int p, ll value) {
t[p] = value+t[p];
if (p < MAX) d[p] += value;
}
void push(int p) {
for (int s = h; s > 0; --s) {
int i = p >> s;
if (d[i] != 0) {
apply(i<<1, d[i]);
apply(i<<1|1, d[i]);
d[i] = 0;
}
}
}
void build(int p) {
while (p > 1) p >>= 1, t[p] = std::min(t[p<<1], t[p<<1|1]) + d[p];
}
void inc(int l, int r, ll value) {
l += MAX, r += MAX;
ll l0 = l, r0 = r;
for (; l < r; l >>= 1, r >>= 1) {
if (l&1) apply(l++, value);
if (r&1) apply(--r, value);
}
build(l0);
build(r0 - 1);
}
ll query(int l, int r) {
l += MAX, r += MAX;
push(l);
push(r - 1);
ll res = inf;
for (; l < r; l >>= 1, r >>= 1) {
if (l&1) res = std::min(res, t[l++]);
if (r&1) res = std::min(t[--r], res);
}
return res;
}
pii vecstack[MAX];
int cur=0;
pii back(void){return vecstack[cur-1];}
int size(void){return cur;}
void push_back(auto x){vecstack[cur]=x;++cur;}
void pop_back(){--cur;}
int solve(int n, int k, int* array){
N=n;
K=k;
expo[0]=1;
for(auto&x:t)x=inf;
for(auto&x:dp)x=inf;
{
ll max=0;
for(int i=0;i!=K;++i){
max=std::max(max,(ll)array[i]);
dp[i]=max;
}
}
for(int i=0;i!=std::min(N,1e6);++i){
pii ent = {array[i],i};
int last_r = i-1;
const int barrier = i-K;
while(size()&&last_r>=barrier&&back().first<=array[i]){
auto ref = back();
int dif = array[i]-ref.first;
inc(ref.second,last_r,dif);
last_r=ref.second-1;
ent.second=ref.second;
pop_back();
}
ent.second=std::max(ent.second,barrier);
push_back(ent);
ll ask = query(std::max(0,barrier),i+1);
dp[i]=std::min(dp[i],ask);
update(i,array[i]+dp[i]);
}
return gera_hash();
}