Submission #1198345

#TimeUsernameProblemLanguageResultExecution timeMemory
1198345biankFish 3 (JOI24_fish3)C++20
28 / 100
1053 ms268616 KiB
#include <bits/stdc++.h> using namespace std; #define forn(i,n) for(int i=0;i<int(n);i++) #define forsn(i,s,n) for(int i=int(s);i<int(n);i++) #define dforn(i,n) for(int i=int(n)-1;i>=0;i--) #define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--) #define fst first #define snd second #define pb push_back #define eb emplace_back #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() typedef long long ll; typedef vector<ll> vll; typedef vector<int> vi; typedef pair<int,int> ii; const ll INF=1e18; template<typename U, typename V> ostream &operator<<(ostream &os, const pair<U, V> &p){ return os<<"("<<p.fst<<", "<<p.snd<<")"; } template<typename T> ostream &operator<<(ostream &os, const set<T> &s){ os<<"{"; bool flag=false; for(const T &x:s){ if(flag) cout<<", "; flag=true; os<<x; } return os<<"}"; } template<typename T> ostream &operator<<(ostream &os, const vector<T> &v){ os<<"["; bool flag=false; for(const T &x:v){ if(flag) cout<<", "; flag=true; os<<x; } return os<<"]"; } ll d; struct Node{ vll vals; vll mini; vll suff; ll cost=0LL; Node(){} Node(vll v){ if(v.empty()) return; vals=v; int n=sz(v); mini.resize(n),suff.resize(n); mini[n-1]=suff[n-1]=vals[n-1]; dforn(i,n-1){ mini[i]=min(mini[i+1],vals[i]); cost+=vals[i]-mini[i]; suff[i]=suff[i+1]+mini[i]; } } }; const int SZ=1<<19; Node st[2*SZ]; ll query(int l, int r){ vi left,right; for(l+=SZ,r+=SZ;l<r;l/=2,r/=2){ if(l&1) left.pb(l++); if(r&1) right.pb(--r); } vi nodes=left; dforn(i,sz(right)) nodes.pb(right[i]); ll mini=INF; ll cost=0; reverse(all(nodes)); for(int u:nodes){ int lo=-1,hi=sz(st[u].mini); while(hi-lo>1){ int mid=(lo+hi)/2; if(st[u].mini[mid]>=mini) hi=mid; else lo=mid; } cost+=st[u].cost; if(hi!=sz(st[u].mini))cost+=st[u].suff[hi]-mini*(sz(st[u].mini)-hi); mini=min(mini,st[u].mini.front()); } return cost; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin>>n>>d; forn(i,n){ ll c; cin>>c; st[i+SZ]=vll{c}; } dforsn(i,1,SZ){ vll v=st[2*i].vals; forn(j,sz(st[2*i+1].vals)) v.pb(st[2*i+1].vals[j]); st[i]=v; } int q; cin>>q; forn(_,q){ int l,r; cin>>l>>r; --l; cout<<query(l,r)<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...