Submission #1179600

#TimeUsernameProblemLanguageResultExecution timeMemory
1179600NonozeFish 3 (JOI24_fish3)C++20
20 / 100
486 ms45476 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define sz(x) (int)x.size() #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define fi first #define se second #define cmin(a, b) a=min(a, b) #define cmax(a, b) a=max(a, b) void solve(); signed main() { ios::sync_with_stdio(0); cin.tie(0); solve(); return 0; } int k; struct node { int nbl, nbr, val, sz; }; struct segtree { int n; vector<node> t; segtree(int _n, vector<int>&a) { n=_n, t.resize(4*n); build(0, 0, n-1, a); } node combine(node l, node r) { int nb=max(0LL, (l.nbr-r.nbl+k-1)/k); int val=l.val+r.val-r.sz*nb; node ans={l.nbl, r.nbr+nb*k, val, l.sz+r.sz}; return ans; } void update(int id) { t[id]=combine(t[id*2+1], t[id*2+2]); } void build(int id, int l, int r, vector<int>&a) { if (l==r) { t[id]={a[l]%k, a[l]%k, a[l]/k, 1}; return; } int mid=(l+r)/2; build(id*2+1, l, mid, a); build(id*2+2, mid+1, r, a); update(id); } node query(int id, int l, int r, int ql, int qr) { if (ql<=l && r<=qr) return t[id]; int mid=(l+r)/2; if (qr<=mid) return query(id*2+1, l, mid, ql, qr); if (ql>mid) return query(id*2+2, mid+1, r, ql, qr); auto L=query(id*2+1, l, mid, ql, min(mid, qr)); auto R=query(id*2+2, mid+1, r, max(mid+1, ql), qr); return combine(L, R); } node query(int l, int r) { return query(0, 0, n-1, l, r); } }; int n, q; vector<int> a; void solve() { cin >> n >> k; a.resize(n); for (auto &u: a) cin >> u; segtree st(n, a); cin >> q; while (q--) { int l, r; cin >> l >> r; l--, r--; node res=st.query(l, r); if (res.nbr>a[r]) { cout << -1 << endl; continue; } int ans=res.val-(r-l+1)*(a[r]-res.nbr)/k; cout << ans << endl; } }
#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...