Submission #912528

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
912528	2024-01-19T15:03:33 Z	andro	Addk (eJOI21_addk)	C++14	100 / 100	442 ms	22012 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	472 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	3 ms	840 KB	Output is correct
4	Correct	4 ms	1052 KB	Output is correct
5	Correct	5 ms	1116 KB	Output is correct
6	Correct	6 ms	1372 KB	Output is correct
7	Correct	9 ms	1628 KB	Output is correct
8	Correct	9 ms	1732 KB	Output is correct
9	Correct	12 ms	2372 KB	Output is correct

Subtask #2

56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	4420 KB	Output is correct
2	Correct	43 ms	6396 KB	Output is correct
3	Correct	69 ms	8564 KB	Output is correct
4	Correct	160 ms	14660 KB	Output is correct
5	Correct	247 ms	20756 KB	Output is correct
6	Correct	235 ms	20412 KB	Output is correct
7	Correct	269 ms	20464 KB	Output is correct

Subtask #3

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	11072 KB	Output is correct
2	Correct	215 ms	17040 KB	Output is correct
3	Correct	442 ms	22012 KB	Output is correct
4	Correct	273 ms	21116 KB	Output is correct