Submission #1272758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272758		hynmj	Fish 3 (JOI24_fish3)	C++20	27 / 100	576 ms	64236 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
const long long N = 3e5 + 5;
int a[N];
int original_A[N];
int b[N];
int c[N]; // count of zeros
int p[N]; // prefix sm
const int lg = 20;
int sp[N][lg];

// Function to initialize the Sparse Table
void initialize(int n, int ls[])
{
    for (int i = 0; i < n; i++)
    {
        sp[i][0] = ls[i];
    }
    for (int i = 1; i < lg; i++)
    {
        for (int j = 0; j + (1ll << i) <= n; j++)
        {
            sp[j][i] = min(sp[j][i - 1], sp[j + (1ll << (i - 1))][i - 1]);
        }
    }
}

// Function to get the minimum value in the range [l, r]
int get(int l, int r)
{
    int ch = 31 - __builtin_clz(r - l + 1);
    return min(sp[l][ch], sp[r - (1ll << ch) + 1][ch]);
}
void solve()
{
    int n, d;
    cin >> n >> d;
    for (int i = 1; i <= n; i++)
    {

        cin >> a[i];
        original_A[i] = a[i];
    }
    for (int i = n; i > 1; i--)
    {
        int k = (a[i - 1] - a[i] + d - 1) / d;
        k = max(k, 0ll);
        b[i - 1] = k;
        a[i - 1] -= d * k;
    }
    initialize(n + 1, b);
    for (int i = 1; i <= n; i++)
    {
        c[i + 1] = c[i] + (b[i] == 0);
        p[i] = p[i - 1] + b[i];
    }
    // for (int i = 0; i <= n; i++)
    // {
    //     cout << a[i] << " ";
    // }
    // cout << endl;
    // for (int i = 0; i <= n; i++)
    // {
    //     cout << b[i] << " ";
    // }
    // cout << endl;
    // for (int i = 0; i <= n; i++)
    // {
    //     cout << c[i] << " ";
    // }
    // cout << endl;
    // for (int i = 0; i <= n; i++)
    // {
    //     cout << p[i] << " ";
    // }
    // cout << endl;
    int q;
    cin >> q;
    int mn, mx;
    for (int i = 0; i < q; i++)
    {
        cin >> mn >> mx;
        int l = mn - 1, r = mx + 1;
        while (r - l > 1)
        {
            int mid = (r + l) / 2;
            (c[mid] < c[mx]) ? (l = mid) : (r = mid);
        }

        {
            r = min(r, mx);
            int k = get(r, mx);
            if (original_A[mn] - (b[mn] - (r == mn) * k) * d < 0)
            {
                cout << -1 << endl;
                continue;
            }
            if (original_A[r] - (b[r] - k) * d < 0)
            {
                cout << -1 << endl;
                continue;
            }

            cout << p[mx - 1] - p[mn - 1] - k * (mx - (r));
            // cout << endl;
            // cout << p[mx - 1] - p[mn - 1] << " " << k * (mx - (r));
        }
        cout << endl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
    return 0;
}

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