제출 #1007590

#제출 시각아이디문제언어결과실행 시간메모리
1007590batsukh2006Fish 3 (JOI24_fish3)C++17
100 / 100
277 ms128488 KiB
#include<iostream> #include<stdio.h> #include<math.h> #include<map> #include<string> #include<algorithm> #include<vector> #include<string.h> #include<utility> #include<set> #include<cmath> #include<queue> #include<deque> #include<functional> #include<stack> #include<limits.h> #include<iomanip> #include<unordered_map> using namespace std; #define MOD 1000000007 #define int long long #define endl '\n' #define ff first #define ss second typedef pair<int,int> pp; void solve(){ int n,d; cin>>n>>d; vector<int> a(n+1); for(int i=1; i<=n; i++) cin>>a[i]; vector<int> dp(n+1),pref(n+2),comp(n+1); dp[n]=a[n]; for(int i=n-1; i>=1; i--){ if(a[i]>dp[i+1]){ comp[i]=((a[i]-dp[i+1])+(d-1))/d; dp[i]=a[i]-((a[i]-dp[i+1])+(d-1))/d*d; pref[i]=pref[i+1]+((a[i]-dp[i+1])+(d-1))/d; }else{ comp[i]=0; dp[i]=a[i]; pref[i]=pref[i+1]; } } stack<int> s; s.push(0); vector<vector<pp> > p(n+1,vector<pp>(20)); for(int i=1; i<=n; i++){ while(s.size()>1&&comp[s.top()]>=comp[i]) s.pop(); p[i][0]=make_pair(s.top(),comp[i]*(i-s.top())); s.push(i); } for(int i=1; i<20; i++){ for(int j=1; j<=n; j++){ p[j][i].ff=p[p[j][i-1].ff][i-1].ff; p[j][i].ss=p[j][i-1].ss+p[p[j][i-1].ff][i-1].ss; } } int q; cin>>q; while(q--){ int l,r; cin>>l>>r; int cur=r,sum=0; int ans=pref[l]-pref[r+1]; for(int i=19; i>=0; i--){ if(p[cur][i].ff>=l){ sum+=p[cur][i].ss; cur=p[cur][i].ff; } } sum+=comp[cur]*(cur-l+1); if(dp[l]+comp[cur]*d<0) cout<<-1<<endl; else cout<<ans-sum<<endl; } } signed main(){ // freopen("hps.in", "r", stdin); // freopen("hps.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--){ solve(); cout<<endl; } 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...