oj.uz

Submission #850494

# Submission time Handle Problem Language Result Execution time Memory
850494 2023-09-16T17:40:51 Z TahirAliyev Addk (eJOI21_addk) C++17
100 / 100
 504 ms 14460 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]);
}

void update(int node, int l, int r, int pos, int val){
    if(l == r){
        tree[node].sum = val;
        tree[node].leftSum = val;
        tree[node].rightSum = val;
        tree[node].s = 1;
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid){
        update(2 * node, l, mid, pos, val);
    }
    else{
        update(2 * node + 1, mid + 1, r, pos, val);
    }
    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{
            vector<int> id;
            vector<int> val;
            for(int i = 0; i < k; i++){
                int a; cin >> a;
                id.push_back(a);
                val.push_back(ask(1, 1, n, a, a).sum);
            }
            for(int i = 0; i < k - 1; i++){
                update(1, 1, n, id[i], val[i + 1]);
            }
            update(1, 1, n, id[k - 1], val[0]);
        }
    }
}

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 600 KB Output is correct
4 Correct 9 ms 2648 KB Output is correct
5 Correct 12 ms 2648 KB Output is correct
6 Correct 15 ms 2648 KB Output is correct
7 Correct 18 ms 2736 KB Output is correct
8 Correct 21 ms 2648 KB Output is correct
9 Correct 34 ms 3048 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2896 KB Output is correct
2 Correct 95 ms 2932 KB Output is correct
3 Correct 130 ms 5200 KB Output is correct
4 Correct 239 ms 10068 KB Output is correct
5 Correct 342 ms 10604 KB Output is correct
6 Correct 328 ms 10704 KB Output is correct
7 Correct 317 ms 10320 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 5200 KB Output is correct
2 Correct 321 ms 12564 KB Output is correct
3 Correct 504 ms 14460 KB Output is correct
4 Correct 356 ms 13392 KB Output is correct