제출 #1198358

#제출 시각아이디문제언어결과실행 시간메모리
1198358biankFish 3 (JOI24_fish3)C++20
57 / 100
1028 ms311904 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; const int SZ=1<<19; 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]; } } }; 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; } struct Node2{ bool flag=false; ll mini=INF,maxi=-INF; int cnt=0; ll cost=0; Node2(){ flag=true; } Node2(ll x){ cnt=1; mini=maxi=x; cost=0; flag=false; } }; Node2 merge(Node2 &a, Node2 &b){ if(a.flag) return b; if(b.flag) return a; Node2 c; ll diff=a.maxi-b.mini; ll k=max((diff+d-1)/d,0LL); c.maxi=b.maxi; assert(a.maxi-d*k<=b.mini); c.mini=a.mini-d*k; c.cnt=a.cnt+b.cnt; c.cost=a.cost+b.cost+k*a.cnt; c.flag=false; return c; } Node2 st2[2*SZ]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin>>n>>d; vll c(n); forn(i,n){ cin>>c[i]; } int q; cin>>q; if(n<=3000&&q<=3000){ forn(_,q){ int l,r; cin>>l>>r; --l; ll mini=INF; ll cost=0; dforsn(i,l,r){ ll k=max((c[i]-mini+d-1)/d,0LL); cost+=k; assert(c[i]-k*d<=mini); mini=c[i]-k*d; } if(mini<0) cout<<"-1\n"; else cout<<cost<<'\n'; } return 0; } bool flag=true; forn(i,n-1) flag&=c[i]>=c[i+1]; if(!flag){ forn(i,n) st[i+SZ]=vll{c[i]}; 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; } forn(_,q){ int l,r; cin>>l>>r; --l; cout<<query(l,r)<<'\n'; } return 0; } forn(i,n){ st2[i+SZ]=c[i]; } dforsn(i,1,SZ){ st2[i]=merge(st2[2*i],st2[2*i+1]); } forn(_,q){ Node2 left,right; int l,r; cin>>l>>r; for(l+=SZ-1,r+=SZ;l<r;l/=2,r/=2){ if(l&1) left=merge(left,st2[l++]); if(r&1) right=merge(st2[--r],right); } Node2 ret=merge(left,right); if(ret.mini<0) cout<<"-1\n"; else cout<<ret.cost<<'\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...