Submission #657432

#TimeUsernameProblemLanguageResultExecution timeMemory
657432drkarlicio2107Peru (RMI20_peru)C++14
49 / 100
410 ms262144 KiB
#include "peru.h" #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 1e18; 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 (int n, int k, 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=1e18; 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; } for (int i=1; i<n+1; i++) sol [i]=sol [i]%MOD; 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; } /*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; }*/

Compilation message (stderr)

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:12:12: warning: 'resi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 |   l [ind]=x+y;
      |           ~^~
peru.cpp:120:17: note: 'resi' was declared here
  120 |   long long int resi, ind=-1;
      |                 ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...