Submission #979395

#	Time	Username	Problem	Language	Result	Execution time	Memory
979395		Andrey	Fish 3 (JOI24_fish3)	C++14	100 / 100	1474 ms	608604 KiB

Main

#include<bits/stdc++.h>
using namespace std;

vector<long long> haha(300001);
vector<long long> wow(1200001);
vector<long long> bruh[12000001];
vector<long long> yay[1200001];
vector<long long> yeah[1200001];
long long sm = LLONG_MAX,ans = 0,d;

void build(long long l, long long r, long long x) {
    bruh[x].push_back(LLONG_MAX);
    yay[x].push_back(0);
    yeah[x].push_back(0);
    long long sb = 0,br = 0;
    for(long long i = r; i >= l; i--) {
        long long c = bruh[x][bruh[x].size()-1];
        long long f = 0;
        if(c < haha[i]) {
            f = (haha[i]-c+d-1)/d;
        }
        wow[x]+=f;
        bruh[x].push_back(haha[i]-f*d);
        long long e = haha[i]-f*d;
        if(c != LLONG_MAX) {
            br+=(c-e)/d;
        }
        yay[x].push_back(br);
        sb+=br;
        yeah[x].push_back(sb);
    }
    if(l == r) {
        return;
    }
    long long m = (l+r)/2;
    build(l,m,x*2);
    build(m+1,r,x*2+1);
}

void calc(long long l, long long r, long long x, long long ql, long long qr) {
    if(l == ql && r == qr) {
        if(sm < 0) {
            return;
        }
        long long bl = 0,br = bruh[x].size()-1;
        ans+=wow[x];
        if(sm >= bruh[x][1]) {
            sm = bruh[x][bruh[x].size()-1];
            return;
        }
        long long c = (bruh[x][1]-sm+d-1)/d;
        while(bl < br) {
            long long mid = (bl+br+1)/2;
            if(yay[x][mid] <= c) {
                bl = mid;
            }
            else {
                br = mid-1;
            }
        }
        ans+=c*bl-yeah[x][bl];
        sm = min(sm,bruh[x][bruh[x].size()-1]-d*(max(0LL,c-yay[x][bruh[x].size()-1])));
        return;
    }
    long long m = (l+r)/2;
    if(qr <= m) {
        calc(l,m,x*2,ql,qr);
    }
    else if(ql > m) {
        calc(m+1,r,x*2+1,ql,qr);
    }
    else {
        calc(m+1,r,x*2+1,m+1,qr);
        calc(l,m,x*2,ql,m);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,q,l,r;
    cin >> n >> d;
    for(long long i = 1; i <= n; i++) {
        cin >> haha[i];
    }
    cin >> q;
    build(1,n,1);
    for(long long i = 0; i < q; i++) {
        ans = 0;
        sm = LLONG_MAX;
        cin >> l >> r;
        calc(1,n,1,l,r);
        if(sm < 0) {
            cout << -1 << "\n";
        }
        else {
            cout << ans << "\n";
        }
    }
    return 0;
}

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