Submission #894615

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
894615	2023-12-28T14:28:20 Z	IWKR	Addk (eJOI21_addk)	C++17	100 / 100	306 ms	22100 KB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

int arr[100001];

struct node {
    int s, e, m, val, incre, decre;
    node *l, *r;
    node(int S, int E) {
        s = S;
        e = E;
        m = (s + e) / 2;
        val = 0; incre = 0; decre = 0;
        if (s != e) {
            l = new node(s, m);
            r = new node(m + 1, e);
        }
    }
    void update(int X, int V) {
        if (s == e) {
            val = V;
            incre = V;
            decre = V;
        } else {
            if (X <= m) {
                l -> update(X, V);
            } else {
                r -> update(X, V);
            }
            val = l -> val + r -> val;
            incre = l -> incre + ((r -> s - l -> s) * r -> val) + r -> incre;
            decre = r -> decre + ((r -> e - l -> e) * l -> val) + l -> decre;
        }
    }
    int query(int S, int E) {
        if (S > E) {
            return 0;
        }
        if (s == S && e == E) {
            return val;
        } else {
            if (E <= m) {
                return l -> query(S, E);
            } else if (S > m) {
                return r -> query(S, E);
            } else {
                return l -> query(S, m) + r -> query(m + 1, E);
            }
        }
    }
    int query2(int S, int E, int left) {
        if (S > E) {
            return 0;
        }
        if (s == S && e == E) {
            return val * (s - left) + incre;
        } else {
            if (E <= m) {
                return l -> query2(S, E, left);
            } else if (S > m) {
                return r -> query2(S, E, left);
            } else {
                return l -> query2(S, m, left) + r -> query2(m + 1, E, left);
            }
        }
    }
    int query3(int S, int E, int right) {
        if (S > E) {
            return 0;
        }
        if (s == S && e == E) {
            return val * (right - e) + decre;
        } else {
            if (E <= m) {
                return l -> query3(S, E, right);
            } else if (S > m) {
                return r -> query3(S, E, right);
            } else {
                return l -> query3(S, m, right) + r -> query3(m + 1, E, right);
            }
        }
    }
} *root;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    root = new node(1, n);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        root -> update(i, arr[i]);
    }
    int q;
    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            vector<int> v;
            vector<int> value;
            for (int i = 0; i < k; i++) {
                int a;
                cin >> a;
                v.push_back(a);
                value.push_back(arr[a]);
            }
            root -> update(v[k - 1], arr[v[0]]);
            for (int i = 0; i < k - 1; i++) {
                root -> update(v[i], arr[v[i + 1]]);
            }
            arr[v[k - 1]] = value[0];
            for (int i = 0; i < k - 1; i++) {
                arr[v[i]] = value[i + 1];
            }
        } else {
            int l, r, m;
            cin >> l >> r >> m;
            if (m > (r - l) / 2 + 1) {
                m = r - l + 2 - m;
            }
            int ans = (root -> query(l + m - 1, r - m + 1)) * m;
            ans += root -> query2(l, l + m - 2, l);
            ans += root -> query3(r - m + 2, r, r);
            cout << ans << '\n';
        }
    }
}

Subtask #1

36.0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	860 KB	Output is correct
3	Correct	2 ms	860 KB	Output is correct
4	Correct	3 ms	992 KB	Output is correct
5	Correct	4 ms	1116 KB	Output is correct
6	Correct	5 ms	1412 KB	Output is correct
7	Correct	7 ms	1628 KB	Output is correct
8	Correct	8 ms	1620 KB	Output is correct
9	Correct	11 ms	2392 KB	Output is correct

Subtask #2

56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	4444 KB	Output is correct
2	Correct	38 ms	6368 KB	Output is correct
3	Correct	58 ms	8620 KB	Output is correct
4	Correct	106 ms	14636 KB	Output is correct
5	Correct	186 ms	20796 KB	Output is correct
6	Correct	158 ms	20564 KB	Output is correct
7	Correct	153 ms	20564 KB	Output is correct

Subtask #3

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	10948 KB	Output is correct
2	Correct	167 ms	17084 KB	Output is correct
3	Correct	306 ms	22100 KB	Output is correct
4	Correct	209 ms	21076 KB	Output is correct