| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 657419 | drkarlicio2107 | Peru (RMI20_peru) | C++14 | 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>
using namespace std;
vector < pair <long long int, pair <long long int, long long int> > > pom;
long long int sol [2500000];
struct mono_stack {
long long int l [2500000]; long long int ind=0;
pair <long long int, pair <long long int, long long int> > pos [2500000];
void push (long long int x, long long int y, long long int z){
l [ind]=x+y;
if (ind!=0) l [ind]=min (l [ind], l [ind-1]);
pos [ind]={x, {y, z}};
ind++;
}
void pop (){
l [ind-1]=0; pos [ind-1]={0, {0, 0}};
ind--;
}
long long int maxi (){
if (ind==0) return 1e9;
return l [ind-1];
}
long long int size (){
return ind;
}
pair <long long int, pair <long long int, long long int> > top (){
return pos [ind-1];
}
pair <long long int, pair <long long int, long long int> > down (){
return pos [0];
}
};
struct mono_deque {
mono_stack l; mono_stack r;
void push_back (long long int x, long long int y, long long int z){
l.push (x, y, z);
}
void push_front (long long int x, long long int y, long long int z){
r.push (x, y, z);
}
void pop_back (){
if (l.size ()!=0) l.pop();
else {
if (r.size()==1){
r.pop(); return ;
}
pom.clear ();
while (r.size()) {
pom.push_back (r.top ()); r.pop();
}
reverse (pom.begin(), pom.end());
for (long long int i=pom.size()/2-1; i>=0; i--) l.push (pom [i].first, pom [i].second.first, pom [i].second.second);
for (long long int i=pom.size()/2; i<(long long int)pom.size(); i++) r.push (pom [i].first, pom [i].second.first, pom [i].second.second);
l.pop();
}
}
void pop_front(){
if (r.size ()!=0) r.pop();
else {
if (l.size()==1){
l.pop(); return ;
}
pom.clear ();
while (l.size()) {
pom.push_back (l.top ()); l.pop();
}
for (long long int i=pom.size()/2-1; i>=0; i--) l.push (pom [i].first, pom [i].second.first, pom [i].second.second);
for (long long int i=pom.size()/2; i<(long long int)pom.size(); i++) r.push (pom [i].first, pom [i].second.first, pom [i].second.second);
r.pop();
}
}
long long int maxi (){
return min (l.maxi (), r.maxi());
}
pair <long long int, pair <long long int, long long int> > top (){
if (r.size()==0) return l.down ();
return r.top();
}
pair <long long int, pair <long long int, long long int> > down (){
if (l.size()==0) return r.down ();
return l.top();
}
long long int size() {
return l.size()+r.size();
}
};
mono_deque d;
long long int t [2500000];
long long int MOD=1e9+7;
int solve (long long int n, long long int k, long long int s []){
/*for (long long int i=0; i<n; i++) {
long long int a; cin >> a;
if (a==1){
long long int x; cin >> x; d.push_back (x);
}
else if (a==2){
long long int x; cin >> x; d.push_front (x);
}
else if (a==3) d.pop_back ();
else{
d.pop_front ();
}
cout << d.maxi() << endl;
}*/
d.push_back (0, 0, 0);
for (long long int i=1; i<n+1; i++){
long long int x; x=s [i-1];
long long int maxi=1e9; long long int ind2; long long int da=0;
while (d.size ()>0 && d.top ().second.first<=x){
pair <long long int, pair <long long int, long long int> > z=d.top ();
maxi=min (maxi, z.first); ind2=z.second.second;
d.pop_front(); da=1;
}
if (da) d.push_front (maxi, x, ind2);
long long int resi, ind=-1;
//my_sol+=x;
while (d.size()>0 && i-k>d.down ().second.second){
resi=d.down().second.first; ind=d.down ().second.second; d.pop_back ();
}
//cout << ind << endl;
if (d.down ().second.second!=ind+1 && ind!=-1) d.push_back (sol [ind+1], resi, ind+1);
sol [i]=d.maxi();
//cout << d.maxi() << " " << d.size() << endl;
d.push_front (sol [i], 0 , i);
//cout << sol [i] << "DA" << endl;
}
long long int ans=0;
t [1]=1;
for (long long int i=2; i<n+1; i++) t [i]=(t [i-1]*23)%MOD;
for (long long int i=1; i<n+1; i++) ans=(ans+sol [i]*t [n-i+1])%MOD;
//for (long long int i=1; i<n+1; i++) cout << sol [i] << " ";
return ans;
}
/*long long int s [2500000];
int main (){
long long int n, k; cin >> n >> k;
for (int i=0; i<n; i++) cin >> s [i];
cout << solve (n, k, s);
return 0;
}*/