oj.uz

Submission #774837

# Submission time Handle Problem Language Result Execution time Memory
774837 2023-07-06T04:02:44 Z giaminh2211 Addk (eJOI21_addk) C++14
100 / 100
 296 ms 8780 KB 
#include "bits/stdc++.h"
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
const int NM = 1e6 + 5;
int n, k, q, a[NM], q1[15], tree1[NM<<2], tree2[NM<<2], tree3[NM<<2];
void build1(int *arr, int id = 1, int l = 1, int r = n) {
    if (l == r) {
        tree1[id] = arr[l];
        return;
    }
    int mid = (l+r) >> 1;
    build1(arr, id<<1, l, mid);
    build1(arr, id<<1|1, mid+1, r);
    tree1[id] = tree1[id<<1] + tree1[id<<1|1];
}
void build2(int *arr, int id = 1, int l = 1, int r = n) {
    if (l == r) {
        tree2[id] = arr[l] * l;
        return;
    }
    int mid = (l+r) >> 1;
    build2(arr, id<<1, l, mid);
    build2(arr, id<<1|1, mid+1, r);
    tree2[id] = tree2[id<<1] + tree2[id<<1|1];
}
void build3(int *arr, int id = 1, int l = 1, int r = n) {
    if (l == r) {
        tree3[id] = arr[l] * (n-l+1);
        return;
    }
    int mid = (l+r) >> 1;
    build3(arr, id<<1, l, mid);
    build3(arr, id<<1|1, mid+1, r);
    tree3[id] = tree3[id<<1] + tree3[id<<1|1];
}
void update1(int pos, int val, int id = 1, int l = 1, int r = n) {
    if (l == r) {
        tree1[id] = val;
        return;
    }
    int mid = (l+r) >> 1;
    if (pos <= mid) update1(pos, val, id<<1, l, mid);
    else update1(pos, val, id<<1|1, mid+1, r);
    tree1[id] = tree1[id<<1] + tree1[id<<1|1];
}
void update2(int pos, int val, int id = 1, int l = 1, int r = n) {
    if (l == r) {
        tree2[id] = val * l;
        return;
    }
    int mid = (l+r) >> 1;
    if (pos <= mid) update2(pos, val, id<<1, l, mid);
    else update2(pos, val, id<<1|1, mid+1, r);
    tree2[id] = tree2[id<<1] + tree2[id<<1|1];
}
void update3(int pos, int val, int id = 1, int l = 1, int r = n) {
    if (l == r) {
        tree3[id] = val * (n-l+1);
        return;
    }
    int mid = (l+r) >> 1;
    if (pos <= mid) update3(pos, val, id<<1, l, mid);
    else update3(pos, val, id<<1|1, mid+1, r);
    tree3[id] = tree3[id<<1] + tree3[id<<1|1];
}
int get(int *tree, int u, int v, int id = 1, int l = 1, int r = n) {
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return tree[id];
    int mid = (l+r) >> 1;
    return get(tree, u, v, id<<1, l, mid) + get(tree, u, v, id<<1|1, mid+1, r);
}
int get_sum1(int l, int r) {
    if (l > r) return 0;
    return get(tree1, l, r);
}
int get_sum2(int l, int r) {
    if (l > r) return 0;
    return get(tree2, l, r) - get_sum1(l, r) * (l-1);
}
int get_sum3(int l, int r) {
    if (l > r) return 0;
    return get(tree3, l, r) - get_sum1(l, r) * (n-r);
}
signed main() {
	IOS;
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) cin >> a[i];
    build1(a);
    build2(a);
    build3(a);
	cin >> q;
	while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            for (int i = 1; i <= k; ++i) cin >> q1[i];
            for (int i = 2; i <= k; ++i) swap(a[q1[i]], a[q1[i-1]]);
            for (int i = 1; i <= k; ++i) {
                update1(q1[i], a[q1[i]]);
                update2(q1[i], a[q1[i]]);
                update3(q1[i], a[q1[i]]);
            }
            continue;
        }
        int l, r, m;
        cin >> l >> r >> m;
        if (r-l+1 < m) {
            cout << "0\n";
            continue;
        }
        int u, v, d = min(r-l+1-m, m-1);
        u = l+d;
        v = r-d;
        cout << get_sum2(l, u-1) + get_sum1(u, v) * (d+1) + get_sum3(v+1, r) << "\n";
	}
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 476 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 6 ms 820 KB Output is correct
7 Correct 8 ms 820 KB Output is correct
8 Correct 11 ms 852 KB Output is correct
9 Correct 14 ms 1236 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2244 KB Output is correct
2 Correct 43 ms 2456 KB Output is correct
3 Correct 60 ms 4300 KB Output is correct
4 Correct 119 ms 7988 KB Output is correct
5 Correct 177 ms 8780 KB Output is correct
6 Correct 151 ms 8544 KB Output is correct
7 Correct 158 ms 8520 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 4308 KB Output is correct
2 Correct 211 ms 8184 KB Output is correct
3 Correct 296 ms 7980 KB Output is correct
4 Correct 190 ms 8688 KB Output is correct