제출 #1062870

#제출 시각아이디문제언어결과실행 시간메모리
1062870matuFish 3 (JOI24_fish3)C++17
0 / 100
2057 ms11060 KiB
#include <bits/stdc++.h> using namespace std; const long double eps = 1e-9; typedef long long ll; typedef long double ld; const int mod = 998244353; struct Mint { int val; Mint(int x = 0) { val = x % mod; } Mint(long long x) { val = x % mod; } Mint operator+(Mint oth) { return val + oth.val; } Mint operator*(Mint oth) { return 1LL * val * oth.val; } Mint operator-(Mint oth) { return val - oth.val + mod; } Mint fp(Mint a, long long n){ Mint p = 1; while(n){ if(n & 1){ p = p * a; } a = a * a; n /= 2; } return p; } Mint operator/(Mint oth){ Mint invers = fp(oth, mod - 2); return 1LL * val * invers.val; } friend ostream& operator << (ostream& os, const Mint& lol){ os << lol.val; return os; } }; struct AINT{ vector<ll> aint, lazy; AINT(int n){ aint.assign(n * 4 + 1, 0); lazy.assign(n * 4 + 1, 0); } void update(int v, int tl, int tr, int l, int r, int val){ if(lazy[v]){ aint[v] += lazy[v]; if(tl != tr){ lazy[v * 2] += lazy[v]; lazy[v * 2 + 1] += lazy[v]; } lazy[v] = 0; } if(l <= tl && r >= tr){ aint[v] += val; if(tl != tr){ lazy[v * 2] += val; lazy[v * 2 + 1] += val; } return; } if(l > tr || r < tl) return; int tm = (tl + tr) / 2; update(v * 2, tl, tm,l,r,val); update(v * 2 + 1, tm + 1, tr, l, r,val); aint[v] = aint[v * 2] + aint[v * 2 + 1]; } ll query(int v, int tl, int tr, int l, int r){ if(lazy[v]){ aint[v] += lazy[v]; if(tl != tr){ lazy[v * 2] += lazy[v]; lazy[v * 2 + 1] += lazy[v]; } lazy[v] = 0; } if(l <= tl && r >= tr) return aint[v]; if(l > tr || r < tl) return 0; int tm = (tl + tr) / 2; return query(v * 2, tl, tm,l, r) + query(v * 2 + 1, tm + 1, tr, l, r); } }; int red =0; int ______________________________________________________________________________________________________________________________________________; void solve(){ ll n, d; cin >> n >> d; vector<ll> v(n + 1), ct(n + 1); for(int i = 1; i <= n; i++){ cin >> v[i]; } // vector<vector<pair<int,int>>> lr(n + 1); // int q; // cin >> q; // for(int i = 1; i <= q; i++){ // int l,r; // cin >> l >> r; // lr[r].push_back({l,i}); // } // AINT aint(n + 1); // for(int i = 1; i <= n; i++){ // aint.update(1,1,n, i,i, v[i]); // } // stack<ll> s; // for(int i = 1; i <= n; i++){ // while(s.size() && v[s.top()] > v[i]){ // aint.update(1,1,n, s.top(), n, ct[s.top()]); // s.pop(); // } // if(s.size()){ // ct[i] = v[i] - v[s.top()]; // aint.update(1,1,n, i, n, -ct[i]); // }else{ // ct[i] = v[i]; // aint.update(1,1,n, 1, n, -ct[i]); // } // s.push(i); // for(auto j : lr[i]){ // } // } int q; cin >> q; while(q--){ int l,r; cin >> l >> r; stack<int> s; vector<ll> mars(n + 2), minim(n + 2, 1e18); ll tl = 0; for(int i = r; i >= l; i--){ minim[i] = min(minim[i + 1], v[i]); } ll ans = 0; ll m1 = 1e18; ll sm = 0; for(int i = l; i <= r; i++){ ll pl = (v[i] - tl + d) %d; if(tl + pl > minim[i]){ ans = -1; break; }else{ tl += pl; m1 = min(m1, (v[i] - tl)); sm += (v[i] - tl); } } if(!ans){ cout << (ll)(sm - (ll)(r-l+1)*m1)/d - (d == 1 ? v[r] - m1 : 0) << '\n'; }else{ cout << ans << '\n'; } } } int32_t main(){ cin.tie(0)->sync_with_stdio(0); int t = 1; if(red) cin >> t; while(t--){ solve(); } } /* 10 10 4 10 2 9 10 4 3 5 1 5 8 7 1 6 8 1 10 15, 12, 9, 3, 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...