Submission #580687

#	Time	Username	Problem	Language	Result	Execution time	Memory
580687		kideso	Addk (eJOI21_addk)	C++17	0 / 100	126 ms	3116 KiB

Main

#include <iostream>
#include <queue>
#include <fstream>

using namespace std;
using ll = long long;

vector<ll> A, B, S, P, rS, rP;
ll N, K, Q;

void build1() {
    S[1] = P[1] = A[1];
    for (ll i = 2; i <= N; ++i) {
        S[i] = S[i - 1] + i * A[i];
        P[i] = P[i - 1] + A[i];
    }
}

void build2() {
    rS[1] = rP[1] = B[1];
    for (ll i = 2; i <= N; ++i) {
        rS[i] = rS[i - 1] + i * B[i];
        rP[i] = rP[i - 1] + B[i];
    }
}

inline ll T(ll i, ll j) {
    return S[j] - S[i - 1] - (i - 1) * (P[j] - P[i - 1]);
}

inline ll rT(ll i, ll j) {
    return rS[j] - rS[i - 1] - (i - 1) * (rP[j] - rP[i - 1]);
}

int main() {
    //ifstream F("be.txt");
    cin >> N >> K;

    A.assign(N + 1, 0); B.assign(N + 1, 0);
    S.assign(N + 1, 0); P.assign(N + 1, 0);
    rS.assign(N + 1, 0); rP.assign(N + 1, 0);

    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        B[N - i + 1] = A[i];
    }

    build1(); build2();

    cin >> Q;
    ll c, l, r, m, k;
    while (Q--) {
        cin >> c;
        if (c == 1) {
            for (int i = 1; i <= K; ++i)
                cin >> k;

            continue;
        }
        else {
            cin >> l >> r >> m;
            ll ans = 0;

            if (m == 1 || m == r - l + 1) ans = P[r] - P[l - 1];
            else if (2 * m <= r - l + 1) ans = T(l, l + m - 1) + rT(N - r + 1, N - r + m) + (r - l + 1 - 2 * m) * (P[r - m] - P[l + m - 1]);
            else {
                k = (r - l + 2) / 2;
                k += l - 1;
                ans = T(l, k) + rT(N - r + 1, N - k);
            }

            cout << ans << '\n';
        }
    }

    return 0;
}

• Subtask 1: 0 / 36
• Subtask 2: 0 / 56
• Subtask 3: 0 / 8