oj.uz

Submission #580692

# Submission time Handle Problem Language Result Execution time Memory
580692 2022-06-21T16:36:31 Z kideso Addk (eJOI21_addk) C++17
92 / 100
 264 ms 8948 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) m = r - l + 2 - m;
                ans = T(l, l + m - 1) + rT(N - r + 1, N - r + m) + m * (P[r - m] - P[l + m - 1]);
            }

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

    return 0;
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 312 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 7 ms 444 KB Output is correct
5 Correct 12 ms 572 KB Output is correct
6 Correct 12 ms 704 KB Output is correct
7 Correct 14 ms 724 KB Output is correct
8 Correct 17 ms 844 KB Output is correct
9 Correct 26 ms 1024 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1508 KB Output is correct
2 Correct 76 ms 2752 KB Output is correct
3 Correct 98 ms 3732 KB Output is correct
4 Correct 180 ms 6356 KB Output is correct
5 Correct 264 ms 8948 KB Output is correct
6 Correct 225 ms 8652 KB Output is correct
7 Correct 222 ms 8708 KB Output is correct

Subtask #3
0 / 8.0

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