oj.uz

Submission #980066

# Submission time Handle Problem Language Result Execution time Memory
980066 2024-05-11T21:13:48 Z TheFuturoma Addk (eJOI21_addk) C++14
92 / 100
 141 ms 9812 KB 
#include <cmath>
#include <algorithm>
#include <bitset>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <array>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	
	int n, k;
    cin>>n>>k;
    if (k > 1) {
        return 0;
    }
    vector<ll> arr(n);
    vector<ll> prefix(1, 0);
    vector<ll> prefix_step(1, 0);
    vector<ll> prefix_step_retard(1, 0);
    for (int i = 0; i < n; i++) {
        cin>>arr[i];
        prefix.push_back(prefix.back() + arr[i]);
        prefix_step.push_back(prefix_step.back() + arr[i] * (i + 1));
        prefix_step_retard.push_back(prefix_step_retard.back() + arr[i] * i);
    }
    reverse(arr.begin(), arr.end());
    vector<ll> suffix(1, 0);
    vector<ll> suffix_step(1, 0);
    vector<ll> suffix_step_retard(1, 0);
    for (int i = 0; i < n; i++) {
        suffix.push_back(suffix.back() + arr[i]);
        suffix_step.push_back(suffix_step.back() + arr[i] * (i + 1));
        suffix_step_retard.push_back(suffix_step_retard.back() + arr[i] * i);
    }
    // reverse(suffix.begin(), suffix.end());
    // reverse(suffix_step.begin(), suffix_step.end());
    reverse(arr.begin(), arr.end());
    int q;
    cin>>q;
    for (int test = 0; test < q; test++) {
        int t;
        cin>>t;
        if (t == 1) {
            int curr;
            cin>>curr;
            continue;
        }
        int left, right, m;
        cin>>left>>right>>m;
        left--;
        right--;
        if (m == right - left + 1 || m == 1) {
            cout << prefix[right + 1] - prefix[left] << endl;
            continue;
        }
        int left_part = min(left + m, right - m + 1);
        int right_part = max(right - m, left + m - 1);
        ll res = 0;
        // cout << left_part << " right_prat" << endl;
        res += prefix_step[left_part] - prefix_step[left] - prefix[left_part] * (left) + prefix[left] * (left);
        // cout << res << " sres" << endl;
        res += suffix_step[n - right_part - 1] - suffix_step[n - right - 1] - suffix[n - right_part - 1] * (n - right - 1) + suffix[n - right - 1] * (n - right - 1);
        // cout << res << " srt" << endl;
        // cout << suffix_step[n - right_part - 1] << endl;
        res += (prefix[right_part + 1] - prefix[left_part]) * min(m, left_part - left + 1);
        cout << res << endl;
    }
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 7 ms 860 KB Output is correct
7 Correct 8 ms 860 KB Output is correct
8 Correct 10 ms 1016 KB Output is correct
9 Correct 14 ms 1336 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2524 KB Output is correct
2 Correct 42 ms 2904 KB Output is correct
3 Correct 58 ms 3300 KB Output is correct
4 Correct 99 ms 5572 KB Output is correct
5 Correct 141 ms 7488 KB Output is correct
6 Correct 132 ms 9812 KB Output is correct
7 Correct 131 ms 9776 KB Output is correct

Subtask #3
0 / 8.0

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