oj.uz

Submission #774733

# Submission time Handle Problem Language Result Execution time Memory
774733 2023-07-06T02:21:27 Z cheat_when_I_was_young Addk (eJOI21_addk) C++17
92 / 100
 55 ms 7388 KB 
// #cheat_when_I_was_young
// #cheatkhitacontre #khionhatoicheat
// #thaycuckythatvong
#include "bits/stdc++.h"
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
const int NM = 1e6 + 5;
int n, k, q, a[NM], p1[NM], p2[NM], p3[NM];
int get_sum1(int l, int r) {
    if (l > r) return 0;
    return p1[r] - p1[l-1];
}
int get_sum2(int l, int r) {
    if (l > r) return 0;
    return p2[r] - p2[l-1] - get_sum1(l, r) * (l-1);
}
int get_sum3(int l, int r) {
    if (l > r) return 0;
    return p3[l] - p3[r+1] - get_sum1(l, r) * (n-r);
}
signed main() {
	IOS;
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        p1[i] = p1[i-1] + a[i];
        p2[i] = p2[i-1] + a[i] * i;
	}
	for (int i = n; i >= 1; --i) p3[i] = p3[i+1] + a[i] * (n-i+1);
	cin >> q;
	while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            for (int i = 1; i <= k; ++i) cin >> x;
            continue;
        }
        int l, r, m;
        cin >> l >> r >> m;
        if (r-l+1 < m) {
            cout << "0\n";
            continue;
        }
        int u, v, d = min(r-l+1-m, m-1);
        u = l+d;
        v = r-d;
        cout << get_sum2(l, u-1) + get_sum1(u, v) * (d+1) + get_sum3(v+1, r) << "\n";
	}
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 4 ms 984 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1220 KB Output is correct
2 Correct 12 ms 2372 KB Output is correct
3 Correct 16 ms 3156 KB Output is correct
4 Correct 38 ms 5316 KB Output is correct
5 Correct 55 ms 7388 KB Output is correct
6 Correct 51 ms 7216 KB Output is correct
7 Correct 42 ms 7176 KB Output is correct

Subtask #3
0 / 8.0

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