제출 #1025117

#제출 시각아이디문제언어결과실행 시간메모리
1025117groguFish 3 (JOI24_fish3)C++14
0 / 100
445 ms80836 KiB
#define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include <bits/stdc++.h> #define ld double #define ll long long #define ull unsigned long long #define llinf 100000000000000000LL // 10^17 #define iinf 2000000000 // 2*10^9 #define pb push_back #define eb emplace_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pii pair<int,int> #define pll pair<ll,ll> #define pld pair<ld,ld> #define all(a) a.begin(),a.end() #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;} #define si(a) (ll)(a.size()) using namespace std; #define maxn 300005 ll n,q,d; ll a[maxn]; ll pa[maxn]; ll b[maxn]; ll c[maxn]; ll pb[maxn]; ll ps[maxn]; pll Q[maxn]; ll fl[maxn]; ll t[2*maxn],ls[2*maxn],rs[2*maxn],tsz = 0,root = 0; pll e[maxn]; vector<pll> ask[maxn]; ll ans[maxn]; ll L[maxn]; ll val[maxn]; ll pv[maxn]; void init(ll &v,ll tl,ll tr){ if(!v) v = ++tsz; if(tl==tr){t[v] = fl[tl];return;} ll mid = (tl+tr)/2; init(ls[v],tl,mid); init(rs[v],mid+1,tr); t[v] = max(t[ls[v]],t[rs[v]]); } ll get(ll v,ll tl,ll tr,ll l,ll r){ if(l>r||l>tr||tl>tr||tl>r) return 0; if(tl>=l&&tr<=r) return t[v]; ll mid = (tl+tr)/2; return max(get(ls[v],tl,mid,l,r),get(rs[v],mid+1,tr,l,r)); } ll t2[2*maxn]; ll lazy[2*maxn]; void init2(ll v,ll tl,ll tr){ if(tl==tr){t2[v] = val[tl];return;} ll mid = (tl+tr)/2; init2(ls[v],tl,mid); init2(rs[v],mid+1,tr); t2[v] = t2[ls[v]] + t2[rs[v]]; } void push(ll v,ll tl,ll tr){ ll mid = (tl+tr)/2; if(lazy[v]==llinf) return; t2[ls[v]]=lazy[v]*(mid-tl+1); t2[rs[v]]=lazy[v]*(tr-(mid+1)+1); lazy[ls[v]]=lazy[v]; lazy[rs[v]]=lazy[v]; lazy[v] = llinf; } ll sum(ll v,ll tl,ll tr,ll l,ll r){ push(v,tl,tr); if(l>r||l>tr||tl>r||tl>tr) return 0; if(tl>=l&&tr<=r) return t2[v]; ll mid = (tl+tr)/2; return sum(ls[v],tl,mid,l,r) + sum(rs[v],mid+1,tr,l,r); } void upd2(ll v,ll tl,ll tr,ll l,ll r,ll x){ push(v,tl,tr); if(l>r||l>tr||tl>r||tl>tr) return; if(tl>=l&&tr<=r){ t2[v]=(tr-tl+1)*x; lazy[v]=x; return; } ll mid = (tl+tr)/2; upd2(ls[v],tl,mid,l,r,x); upd2(rs[v],mid+1,tr,l,r,x); t2[v] = t2[ls[v]] + t2[rs[v]]; } void tc(){ cin >> n >> d; for(ll i = 1;i<=n;i++) cin >> a[i]; for(ll i = 0;i<=2*n;i++) lazy[i] = llinf; stack<ll> st; for(ll i = 1;i<=n;i++){ while(si(st)&&a[st.top()]>a[i]) st.pop(); if(si(st)) L[i] = st.top(); st.push(i); } for(ll i = 1;i<=n;i++) e[i] = {a[i],i}; for(ll i = 1;i<=n;i++) c[i] = a[i]%d; for(ll i = 1;i<=n;i++) pa[i] = pa[i-1] + a[i]; cin >> q; for(ll i = 1;i<=q;i++){ cin >> Q[i].fi >> Q[i].sc; ask[Q[i].sc].pb({Q[i].fi,i}); } for(ll i = 2;i<=n;i++){ b[i] = c[i]-c[i-1]; if(b[i]<0) b[i]+=d; ps[i] = ps[i-1] + b[i]; } for(ll i = 1;i<=n;i++) pb[i] = pb[i-1] + b[i]*i; for(ll i = 1;i<=n;i++){ ll tl = 1,tr = i,mid,rez = i; while(tl<=tr){ mid = (tl+tr)/2; if(ps[i]-ps[mid]+c[mid]<=a[i]) rez = mid,tr = mid-1; else tl = mid+1; } fl[i] = rez; } init(root,1,n); for(ll i = 1;i<=n;i++) val[i] = a[i] - ps[i]; for(ll i = 1;i<=n;i++) pv[i] = pv[i-1] + val[i]; init2(root,1,n); //ceri(L,1,n); sort(e+1,e+1+n); for(ll j = 1;j<=n;j++){ ll r = e[j].sc; //cerr<<"AAA: "<<L[r]+1<< " "<<r<<endl; upd2(root,1,n,L[r]+1,r-1,val[r]); for(pll p : ask[r]){ ll l = p.fi; ll gr = get(root,1,n,l,r); if(gr>l){ ans[p.sc] = -1; continue; } ll uk = 0; //uk+=pa[r]-pa[l-1]; //uk+=(ps[r]-ps[l]+c[l]); uk+=(pv[r]-pv[l-1]) - sum(root,1,n,l,r); //cerr<<"LR: "<<l<< " "<<r<< " "<<sum(root,1,n,l,r)<<endl; ans[p.sc] = uk/d; } } for(ll i = 1;i<=q;i++) cout<<ans[i]<<endl; } /** 6 3 16 14 13 8 6 5 4 1 4 2 5 3 3 1 6 5 1 3 1 4 1 5 3 1 5 2 4 3 5 **/ int main(){ ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); int t; t = 1; while(t--){ tc(); } return (0-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...