Submission #774830

#	Time	Username	Problem	Language	Result	Execution time	Memory
774830		giaminh2211	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	0 / 100	109 ms	58312 KiB

worst_reporter3

#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: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 81