Submission #1025039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025039		grogu	Fish 3 (JOI24_fish3)	C++14	20 / 100	117 ms	32080 KiB

Main

#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];
void tc(){
    cin >> n >> d;
    for(ll i = 1;i<=n;i++) cin >> a[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;
    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<=q;i++){
        ll l = Q[i].fi,r = Q[i].sc;
        ll s = ps[r]-ps[l]+c[l];
        if(s<=a[r]){
            ll uk = pa[r]-pa[l-1];
            ll len = r-l+1;
            ll del = a[r]-s;
            uk-=del*len;
            uk-=(r+1)*(ps[r]-ps[l]+c[l])-(pb[r]-pb[l]+c[l]*l);
            cout<<uk/d<<endl;
        }else cout<<-1<<endl;
    }
}
/**
6 3
16 14 13 8 6 5
4
1 4
2 5
3 3
1 6
**/
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);
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 7
• Subtask 3: 0 / 28
• Subtask 4: 20 / 20
• Subtask 5: 0 / 36