제출 #1112236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112236		zxcigan	Fish 3 (JOI24_fish3)	C++17	9 / 100	2084 ms	24596 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), a(n + 1), b(n + 1);
    vector<int>p2(n + 1);
    vector<int>p3(n + 1);
    vector<int>p4(n + 1);

    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
        a[i] = c[i] / d;
        b[i] = c[i] % d;
        pref[i] = pref[i - 1] + c[i];
        p2[i] = p2[i - 1] + a[i];
    }
    for (int i = 1; i < n; ++i) {
        p3[i] = p3[i - 1] + bool (b[i] > b[i + 1]);
        p4[i] = p4[i - 1] + (b[i] > b[i + 1] ? i : 0);
    }
    int q; cin >> q;
    vector<int> id(n + 1);
    for (int i = 1; i <= n; ++i) {
        int nw = a[i];
        for (int j = i - 1; j >= 1; j -= 1) {
            if (a[j] >= nw) {
                if (b[j] > b[j + 1]) nw -= 1;
            } else {
                id[i] = j;
                break;
            }
        }
    }
    while (q--) {
        int l, r; cin >> l >> r;
        int wr = r;
        int ans = 0;
        bool bad = 0;
        int mnO = a[r];
//        r -= 1;
//        while (r >= l) {
//            if (a[r] >= mnO) {
//                if (b[r] > b[r + 1]) {
//                    mnO -= 1;
//                }
//                ans += a[r] - mnO;
//            }
//            else {
//                mnO = a[r];
//            }
//            --r;
//            if (mnO < 0) bad = 1;
//        }
//
//        cout << (!bad ? ans : -1) << '\n';
        r = wr;
        ans = 0;
        bad = 0;
        mnO = a[r];

        while (r >= l) {
            int ps = max (l, id[r] + 1);
            ans += p2[r - 1] - p2[ps - 1];
            mnO = a[r];
            ans -= mnO * (r - ps);
            int all = p4[r - 1] - p4[ps - 1];
            int cnt = p3[r - 1] - p3[ps - 1];
            ans += all - (ps - 1) * cnt;
            r = id[r];
            if (mnO < cnt) {
                bad = 1;
                break;
            }
        }

        cout << (!bad ? ans : -1) << '\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;
}

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