Submission #1120045

#TimeUsernameProblemLanguageResultExecution timeMemory
1120045Math4Life2020Fish 3 (JOI24_fish3)C++17
0 / 100
2076 ms86316 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll,ll>; const ll Nm = 524288; const ll E = 19; ll rmqv[Nm][E+1]; void initRMQ(vector<ll> b) { ll N = b.size(); for (ll i=0;i<N;i++) { rmqv[i][0]=b[i]; } for (ll j=1;j<=E;j++) { for (ll i=0;i<(N-(1LL<<j)+1);i++) { rmqv[i][j]=min(rmqv[i][j-1],rmqv[i+(1LL<<(j-1))][j-1]); } } } ll l2(ll x) { return (31-__builtin_clz(x)); } ll rmq(ll a, ll b) { ll l = l2(b-a+1); return min(rmqv[a][l],rmqv[b-(1LL<<l)+1][l]); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll N,D; cin >> N >> D; ll c[N]; ll rem[N]; ll d0[N]; ll a[N]; vector<ll> b; for (ll i=0;i<N;i++) { cin >> c[i]; rem[i]=c[i]%D; d0[i]=c[i]/D; } a[0]=0; b.push_back(d0[0]); for (ll i=1;i<N;i++) { if (rem[i-1]>rem[i]) { a[i]=a[i-1]+1; } else { a[i]=a[i-1]; } b.push_back(a[i]+d0[i]); } ll psb[N+1]; psb[0]=0; for (ll i=0;i<N;i++) { psb[i+1]=psb[i]+b[i]; } initRMQ(b); ll Q; cin >> Q; ll ans[Q]; vector<pii> qr[N]; //qr[right]={left,qryIndex} for (ll q=0;q<Q;q++) { ll l,r; cin >> l >> r; l--; r--; qr[r].push_back({l,q}); } vector<pii> cnums; //{value,x-coord} //in strictly INCREASING order for (ll r=0;r<N;r++) { while (!cnums.empty()) { ll vb = cnums.back().first; if (vb>=a[r]) { cnums.pop_back(); } else { break; } } cnums.push_back({a[r],r}); for (pii qrn: qr[r]) { ll l = qrn.first; ll q = qrn.second; if (rmq(l,r)<a[l]) { ans[q]=-1; continue; } ll vf = 0; for (ll i=l;i<=r;i++) { vf += (b[i]-rmq(i,r)); } ans[q]=vf; } } for (ll q=0;q<Q;q++) { cout << ans[q]<<"\n"; } }
#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...