oj.uz

답안 #829557

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829557 2023-08-18T12:50:55 Z vuavisao Addk (eJOI21_addk) C++17
100 / 100
 155 ms 12620 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;

const ll N = 1e5 + 10;

struct SegTree {
    struct Node {
        ll val[2] = {0, 0};  
        Node() {};
        Node operator + (const Node& other) const {
            Node res;
            res.val[0] = this -> val[0] + other.val[0]; 
            res.val[1] = this -> val[1] + other.val[1]; 
            return res;
        }
    };

    ll n_node = 0;
    vector<Node> tree = {};

    void resize(ll _n) { n_node = _n; tree.resize((n_node << 2) + 10); };
    SegTree() {};
    SegTree(ll _n) { this -> resize(_n); };

    void update(ll node, ll l, ll r, ll idx, ll val) {
        if(l == r) {
            tree[node].val[0] = val;
            tree[node].val[1] = val * idx;
            return;
        }
        ll mid = (l + r) >> 1;
        if(idx <= mid) update(node << 1, l, mid, idx, val);
        else update(node << 1 | 1, mid + 1, r, idx, val);
        tree[node] = tree[node << 1] + tree[node << 1 | 1];
    }

    void Update(ll idx, ll val) {
        return update(1, 1, n_node, idx, val);
    }

    Node query(ll node, ll l, ll r, ll L, ll R) {
        if(l > r || L > R || l > R || L > r) return Node();
        if(L <= l && r <= R) return tree[node]; 
        ll mid = (l + r) >> 1;
        return query(node << 1, l, mid, L, R) + query(node << 1 | 1, mid + 1, r, L, R);
    }

    Node Query(ll l, ll r) {
        return query(1, 1, n_node, l, r);
    }
};

ll n, q, k; 
ll a[N];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> k;
    for(ll i = 1; i <= n; ++ i) cin >> a[i];
    cin >> q;
    SegTree st(n);
    for(ll i = 1; i <= n; ++ i) st.Update(i, a[i]);
    while(q-- > 0) {
        ll type; cin >> type;
        if(type == 1) {
            ll List[12], val_in_list[12];
            for(ll i = 1; i <= k; ++ i) cin >> List[i], val_in_list[i] = a[List[i]];
            for(ll i = 1; i <= k; ++ i) {
                ll j = i + 1;
                if(j > k) j -= k;
                a[List[i]] = val_in_list[j];
                st.Update(List[i], a[List[i]]);
            }
        }
        else {
            ll l, r, m; cin >> l >> r >> m;
            // ll le_can_first = l, le_can_last = r - m + 1;
            ll use_last = r - m + 1, use_first = l + m - 1;
            ll res = 0;
            res += st.Query(use_last, use_first).val[0] * (r - m + 1 - l + 1);
            const auto& tmp1 = st.Query(max(use_last, use_first + 1), r);
            res += (r + 1) * tmp1.val[0] - tmp1.val[1];
            const auto& tmp2 = st.Query(l, min(use_last - 1, use_first));
            res += tmp2.val[1] - (l - 1) * tmp2.val[0];
            res += st.Query(use_first + 1, use_last - 1).val[0] * m;
            cout << res << '\n';
        }
    }
    return (0 ^ 0);
}

/// Code by vuavisao

Subtask #1
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 7 ms 852 KB Output is correct
7 Correct 6 ms 856 KB Output is correct
8 Correct 7 ms 980 KB Output is correct
9 Correct 10 ms 1396 KB Output is correct

Subtask #2
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 2516 KB Output is correct
2 Correct 31 ms 3568 KB Output is correct
3 Correct 44 ms 4652 KB Output is correct
4 Correct 79 ms 7984 KB Output is correct
5 Correct 120 ms 11260 KB Output is correct
6 Correct 106 ms 11092 KB Output is correct
7 Correct 107 ms 11044 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 4756 KB Output is correct
2 Correct 104 ms 9388 KB Output is correct
3 Correct 155 ms 12620 KB Output is correct
4 Correct 125 ms 11548 KB Output is correct