제출 #990673

#제출 시각아이디문제언어결과실행 시간메모리
990673starchanFish 3 (JOI24_fish3)C++17
100 / 100
551 ms111956 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define in array<int, 2> #define pb push_back #define pob pop_back #define INF (int)1e17 #define fast() ios_base::sync_with_stdio(false); cin.tie(NULL) const int LOGM = 19; const int MX = 3e5+5; signed main() { fast(); int n, d; cin >> n >> d; vector<int> c(n+1); vector<int> off(n+1, 0); for(int i = 1; i <= n; i++) cin >> c[i]; vector<int> a(n+1), pref(n+1, 0); pref[1] = a[1] = c[1]/d; for(int i = 2; i <= n; i++) { off[i] = off[i-1] + ((c[i]%d) < (c[i-1]%d)); a[i] = (c[i]/d) - off[i]; pref[i] = a[i] + pref[i-1]; } //immediate left that is smaller. int L[LOGM][n+1]; L[0][0] = 0; a[0] = -INF; int S[LOGM][n+1]; S[0][0] = 0; for(int i = 1; i <= n; i++) { L[0][i] = i-1; while(a[L[0][i]] >= a[i]) L[0][i] = L[0][L[0][i]]; S[0][i] = a[i]*(i-L[0][i]); } for(int i = 1; i < LOGM; i++) { for(int j = 0; j <= n; j++) { L[i][j] = L[i-1][L[i-1][j]]; S[i][j] = S[i-1][j]+S[i-1][L[i-1][j]]; } } int q; cin >> q; while(q--) { int l, r; cin >> l >> r; int SS = pref[r]-pref[l-1]; for(int i = LOGM-1; i >= 0; i--) { if(L[i][r] >= l) { SS-=S[i][r]; r = L[i][r]; } } SS-=(a[r]*(r-l+1)); if(a[r] < (-off[l])) SS = -1; cout << SS << "\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...