Submission #475825

#	Time	Username	Problem	Language	Result	Execution time	Memory
475825		prvocislo	Addk (eJOI21_addk)	C++17	0 / 100	178 ms	10140 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;

const int maxn = 1 << 17;
struct node
{
    ll stepup, stepdown, sum;
    int l, r;
} st[maxn * 2];
void update(int i, int x, int vr = 0)
{
    if (i < st[vr].l || i > st[vr].r) return;
    if (st[vr].l == st[vr].r)
    {
        st[vr].stepdown = st[vr].stepup = st[vr].sum = x;
        return;
    }
    update(i, x, vr*2+1);
    update(i, x, vr*2+2);
    st[vr].sum = st[vr*2+1].sum + st[vr*2+2].sum;
    st[vr].stepup = st[vr*2+1].stepup + st[vr*2+2].stepup + st[vr*2+2].sum * (st[vr*2+2].r - st[vr*2+2].l + 1);
    st[vr].stepdown = st[vr*2+1].stepdown + st[vr*2+1].sum * (st[vr*2+1].r - st[vr*2+1].l + 1) + st[vr*2+2].stepdown;
}
ll sum(int li, int ri, int vr = 0)
{
    if (ri < st[vr].l || li > st[vr].r) return 0;
    if (li <= st[vr].l && st[vr].r <= ri) return st[vr].sum;
    return sum(li, ri, vr*2+1) + sum(li, ri, vr*2+2);
}
ll sumup(int li, int ri, int vr = 0)
{
    if (ri < st[vr].l || li > st[vr].r) return 0;
    if (li <= st[vr].l && st[vr].r <= ri) return st[vr].stepup + (st[vr].l - li) * 1ll * st[vr].sum;
    return sumup(li, ri, vr*2+1) + sumup(li, ri, vr*2+2);
}
ll sumdown(int li, int ri, int vr = 0)
{
    if (ri < st[vr].l || li > st[vr].r) return 0;
    if (li <= st[vr].l && st[vr].r <= ri) return st[vr].stepdown + (ri - st[vr].r) * 1ll * st[vr].sum;
    return sumdown(li, ri, vr*2+1) + sumdown(li, ri, vr*2+2);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = maxn - 1; i < maxn * 2; i++) st[i].l = st[i].r = i - (maxn - 1);
    for (int i = maxn - 2; i >= 0; i--) st[i].l = st[i*2+1].l, st[i].r = st[i*2+2].r;
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n), i(k);
    for (int j = 0; j < n; j++)
    {
        cin >> a[j];
        update(j, a[j]);
    }
    int q; cin >> q;
    while (q--)
    {
        int typ; cin >> typ;
        if (typ == 1)
        {
            for (int j = 0; j < k; j++) cin >> i[j], i[j]--, b[i[j]] = a[i[j]];
            for (int j = 0; j < k; j++) a[i[j]] = a[i[(j + 1) % k]], update(i[j], a[i[j]]);
        }
        else
        {
            int l, r, m; cin >> l >> r >> m; l--, r--;
            m = min(m - 1, (r - l) / 2);
            int l1 = l + (m - 1), r1 = r - (m - 1);
            ll ans = sumup(l, l1) + sum(l1 + 1, r1 - 1) * (m + 1) + sumdown(r1, r);
            cout << ans << "\n";
        }
    }
    return 0;
}

• Subtask 1: 0 / 36
• Subtask 2: 0 / 56
• Subtask 3: 0 / 8