oj.uz

Submission #850491

# Submission time Handle Problem Language Result Execution time Memory
850491 2023-09-16T17:33:26 Z TahirAliyev Addk (eJOI21_addk) C++17
92 / 100
 347 ms 13320 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define oo 1e9
#define pii pair<ll, int>

struct DATA{
    ll sum = 0, leftSum = 0, rightSum = 0, s = 0;
};

const int MAX = 1e5 + 5;
int n, k, q;
int arr[MAX];
DATA tree[4 * MAX];

DATA combine(DATA a, DATA b){
    DATA c;
    c.sum = a.sum + b.sum;
    c.leftSum = a.leftSum + b.leftSum + a.s * b.sum;
    c.rightSum = b.rightSum + a.rightSum + b.s * a.sum;
    c.s = a.s + b.s;
    return c;
}

void build(int node, int l, int r){
    if(l == r){
        tree[node].sum = arr[l];
        tree[node].leftSum = arr[l];
        tree[node].rightSum = arr[l];
        tree[node].s = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
}

DATA ask(int node, int l, int r, int ql, int qr){
    if(r < ql || qr < l) return DATA();
    if(ql <= l && r <= qr){
        return tree[node];
    }
    int mid = (l + r) / 2;
    return combine(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql ,qr));
}

ll findAns(int l, int r){
    if(l > r) return 0;
    int mid = (l + r) / 2;
    return ask(1, 1, n, l, mid).leftSum + ask(1, 1, n, mid + 1, r).rightSum;
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    build(1, 1, n);
    cin >> q;
    while(q--){
        int t; cin >> t;
        if(t == 2){
            int l, r, m; cin >> l >> r >> m;
            int s = r - l + 1;
            m = min(m, (s + 1) - m);
            cout << findAns(l, r) - findAns(l + m, r - m) << '\n';
        }
        else{
            for(int i = 1; i <= k; i++){
                int a; cin >> a;
            }
        }
    }
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 6 ms 596 KB Output is correct
4 Correct 10 ms 2760 KB Output is correct
5 Correct 12 ms 2652 KB Output is correct
6 Correct 15 ms 2652 KB Output is correct
7 Correct 18 ms 2652 KB Output is correct
8 Correct 22 ms 2904 KB Output is correct
9 Correct 30 ms 2868 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 3144 KB Output is correct
2 Correct 108 ms 3668 KB Output is correct
3 Correct 135 ms 6412 KB Output is correct
4 Correct 240 ms 11856 KB Output is correct
5 Correct 347 ms 13216 KB Output is correct
6 Correct 307 ms 12884 KB Output is correct
7 Correct 319 ms 13320 KB Output is correct

Subtask #3
0 / 8.0

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