제출 #1112204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112204		zxcigan	Fish 3 (JOI24_fish3)	C++17	64 / 100	516 ms	113948 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);
    bool flag = 1;
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
        if (i != 1 && c[i] > c[i - 1]) flag = 0;
        a[i] = c[i] / d;
        b[i] = c[i] % d;
        pref[i] = pref[i - 1] + c[i];
    }
    int q; cin >> q;
    if (flag) {
        vector<int> p2 (n + 1, 0);
        vector<int> p3 (n + 1, 0);
        vector<int> p4 (n + 1, 0);
        for (int i = 1; i < n; ++i) p4[i] = p4[i - 1] + (b[i] > b[i + 1] ? i : 0);
        for (int i = 1; i < n; ++i) p3[i] = p3[i - 1] + bool (b[i] > b[i + 1]);
        for (int i = 1; i <= n; ++i) p2[i] = p2[i - 1] + a[i];
        while (q--) {
            int ans = 0;
            int l, r, res = 0; cin >> l >> r;

            int mnD = a[r], C = 0;
            r -= 1;
            int kol = p3[r] - p3[l - 1];
            if (mnD < kol) cout << "-1\n";
            ans = p2[r] - p2[l - 1];
            ans -= mnD * (r - l + 1);
            C = (p4[r] - p4[l - 1]) - (l - 1) * kol;
            ans += C;
            if (mnD >= kol) cout << ans << '\n';
        }
        return;
    }
    if (d == 1) {
        vector<int> smalL (n + 1, 0);
        vector<int>v;
        for (int i = 1; i <= n; ++i) {
            while ((int)v.size() && c[v.back()] >= c[i]) v.pop_back();
            if ((int)v.size()) smalL[i] = v.back();
            v.push_back(i);
        }
        vector<vector<int>> binup (20, vector<int> (n + 1));
        vector<vector<int>> cost (20, vector<int> (n + 1));

        for (int i = n; i >= 1; --i) {
            binup[0][i] = smalL[i];
            cost[0][i] += pref[i] - pref[smalL[i]] - (i - smalL[i]) * c[i];
        }
        for (int j = 1; j < 20; ++j) {
            for (int i = 1; i <= n; ++i) {
                binup[j][i] = binup[j - 1][binup[j - 1][i]];
                cost[j][i] = cost[j - 1][i] + cost[j - 1][binup[j - 1][i]];
            }
        }
        while (q--) {
            int l, r;
            cin >> l >> r;
            int ans = 0;
            int v = r;
            for (int pw = 19; pw >= 0; --pw) {
                if (binup[pw][v] > l) {
                    ans += cost[pw][v];
                    v = binup[pw][v];
                }
            }
            int id = max (smalL[v] + 1, l);
            ans += pref[v] - pref[id - 1] - (v - id + 1) * c[v];
            cout << ans << '\n';
        }
        return;
    }
    if (n <= (int)3e3 && q <= (int)3e3) {
        while (q--) {
            int l, r; cin >> l >> 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';

        }
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void solve()':
Main.cpp:33:23: warning: unused variable 'res' [-Wunused-variable]
   33 |             int l, r, res = 0; cin >> l >> r;
      |                       ^~~
Main.cpp:115:22: warning: unused variable 'wr' [-Wunused-variable]
  115 |         int ans = 0, wr = r;
      |                      ^~

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