Submission #1209292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209292		Ekber_Ekber	Addk (eJOI21_addk)	C++20	92 / 100	140 ms	27960 KiB

Main

#include <bits/stdc++.h>
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;

struct point{
    int p, s, sum, sz;
};

constexpr int MAX = 2e+5 + 1, INF = 2e+15, MOD = 1e+9 + 7, K = 31;
vector <point> t(4*MAX+2);

void merge(point &a, point &b, point &c) {
    a.p = b.p + b.sum * c.sz + c.p;
    a.s = c.s + c.sum * b.sz + b.s;
    a.sz = b.sz + c.sz;
    a.sum = b.sum + c.sum;
}

void build(int v, int tl, int tr, vector <int> &a) {
    if (tl == tr) {
        t[v].sum = t[v].p = t[v].s = a[tl];
        t[v].sz = 1;
        return;
    }
    int tm = (tl + tr) / 2;
    build(v*2, tl, tm, a);
    build(v*2+1, tm+1, tr, a);
    merge(t[v], t[v*2], t[v*2+1]);
}

point find(int v, int tl, int tr, int l, int r) {
    if (l > r) {
        point x;
        x.sum = x.p = x.s = x.sz = 0;
        return x;
    }
    if (tl == l && r == tr) return t[v];
    int tm = (tl + tr) / 2;
    point r1 = find(v*2, tl, tm, l, min(r, tm));
    point r2 = find(v*2+1, tm+1, tr, max(l, tm+1), r);
    point res;
    merge(res, r1, r2);
    return res;
}

void upd(int v, int tl, int tr, int i, int x) {
    if (tl == tr) {
        t[v].sum = t[v].p = t[v].s = x;
        t[v].sz = 1;
        return;
    }
    int tm = (tl + tr) / 2;
    if (i <= tm) {
        upd(v*2, tl, tm, i, x);
    }
    else {
        upd(v*2+1, tm+1, tr, i, x);
    }
    merge(t[v], t[v*2], t[v*2+1]);
}

void _() {
    int n, k;
    cin >> n >> k;
    vector <int> v(n);
    for (int &i : v) cin >> i;
    build(1, 0, n-1, v);
    int q;
    cin >> q;
    while (q--) {
        int d;
        cin >> d;
        if (d == 1) {
            vector <int> a(k);
            for (int &i : a) cin >> i, i--;
            for (int i=0; i < k; i++) {
                int x = (i + 1) % k;
                upd(1, 0, n-1, a[i], v[a[x]]);
            }
        }
        else {
            int l, r, m;
            cin >> l >> r >> m;
            --l; --r;
            if (m == 1 || r - l + 1 == m) {
                point x = find(1, 0, n-1, l, r);
                cout << x.sum << endl;
                continue;
            }
            if (r - l + 1 >= (m-1)*2) {
                int i = m - 1;
                point xl = find(1, 0, n-1, l, l+i-1);
                point xr = find(1, 0, n-1, r-i+1, r);
                point x = find(1, 0, n-1, l+i, r-i);
                cout << xl.s + xr.p + x.sum * m << endl;
            }
            else {
                int i = r - l + 1 - m;
                point xl = find(1, 0, n-1, l, l+i-1);
                point xr = find(1, 0, n-1, r-i+1, r);
                point x = find(1, 0, n-1, l+i, r-i);
                cout << xl.s + xr.p + x.sum * (i + 1) << endl;
            }
        }
    }
}

signed main() {
    GOOD_LUCK
    int tests = 1;
    // cin >> tests;
    for (int i = 1; i <= tests; i++) {
        _();
        // cout << endl;
    }
    return 0;
}

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