oj.uz

Submission #580686

# Submission time Handle Problem Language Result Execution time Memory
580686 2022-06-21T15:49:45 Z kideso Addk (eJOI21_addk) C++17
0 / 100
 133 ms 3144 KB 
#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, m) + rT(N - r + 1, N - r + m) + (r - l + 1 - 2 * m) * (P[r - m] - P[m]);
            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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 1484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 3144 KB Output isn't correct
2 Halted 0 ms 0 KB -