Submission #850494

#	Time	Username	Problem	Language	Result	Execution time	Memory
850494		TahirAliyev	Addk (eJOI21_addk)	C++17	100 / 100	504 ms	14460 KiB

Main

#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 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8