Submission #1111758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111758		zxcigan	Fish 3 (JOI24_fish3)	C++17	16 / 100	71 ms	9288 KiB

Main

#include <bits/stdc++.h>

using namespace std;

mt19937_64 rng(time(0));

using ll = long long;
#define int long long

const int N = 2e5 + 1;

void solve() {
    int n, d; cin >> n >> d;
    vector<int> c(n + 1), pref (n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
        pref[i] = pref[i - 1] + c[i];
    }
    int q; cin >> q;
    if (n <= (int)3e3 && q <= (int)3e3) {
        while (q--) {
            int l, r; cin >> l >> r;
            vector<int> a = c;
            int res = 0;
            bool bad = 0;
            for (int i = r - 1; i >= l; --i) {
                if (a[i] > a[i + 1]) {
                    int p = (a[i] - a[i + 1] + d - 1) / d;
                    res += p;
                    a[i] -= p * d;
                }
                if (a[i] < 0) {
                    bad = 1;
                    break;
                }
            }
            cout << (!bad ? res : -1) << '\n';
        }
        return;
    }
    vector<int> mxl (n + 1);
    for (int i = 1; i <= n; ++i) {
        if (c[i]) mxl[i] = mxl[i - 1] + 1;
    }
    while (q--) {
        int l, r; cin >> l >> r;
        int ans = 0, wr = r;
        r -= mxl[r];
        if (r >= l) ans = pref[r] - pref[l - 1];
        if (ans) {
            if (d > 1) {
                cout << "-1\n";
                continue;
            }
        }
        cout << ans << '\n';
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // LOCAL
    int T = 1;
    while (T--) solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:47:22: warning: unused variable 'wr' [-Wunused-variable]
   47 |         int ans = 0, wr = r;
      |                      ^~

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