Submission #477719

#	Time	Username	Problem	Language	Result	Execution time	Memory
477719		chungdinh	Addk (eJOI21_addk)	C++14	100 / 100	405 ms	5680 KiB

Main

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#include <cassert>
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define ll long long
#define ii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define r first
#define c second

#define all(x) x.begin(), x.end()

ostream& operator << (ostream& os, pair<int, int> a) {
    return os << a.first << " : " << a.second;
}

#define endl '\n'
#define db(val) "["#val" = "<<(val)<<"] "
#define cntbit(x) __builtin_popcount(x)

const int N = 2e5 + 5;
const int iINF = 1e9;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1e18;

int n, k;
ll a[N];

ll LL[N], SS[N];

void upd(ll bit[N], int v, ll val) {
    for (; v <= n; v += v & -v) bit[v] += val;
}
ll get(ll bit[N], int v) {
    ll res = 0;
    for (;v >= 1; v -= v & -v) res += bit[v];
    return res;
}
ll point(ll bit[N], int v) {return get(bit, v) - get(bit, v - 1);}
ll sum(ll bit[N], ll l, ll r) {return get(bit, r) - get(bit, l - 1);}

ll f(int l, int r) {
    return sum(LL, l, r) - (sum(SS, l, r)*(l - 1));
}

int main() {
    #ifdef CHUNGDINH
    freopen("main.inp","r",stdin);
    //freopen("main.out","w",stdout);
    #endif
    memset(LL, 0, sizeof LL);
    memset(SS, 0, sizeof SS);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {
        upd(LL, i, (ll)i * a[i]);
        upd(SS, i, a[i]);
    }

    int q; cin >> q;
    while (q--) {
        int ss; cin >> ss;

        if (ss == 1) {
            int id[10], val[10];
            for (int i = 0; i < k; i++) cin >> id[i];

            for (int i = 0; i < k; i++) val[i] = point(SS, id[(i + 1) % k]);
            for (int i = 0; i < k; i++) {
                upd(SS, id[i], -point(SS, id[i]) + val[i]);
                upd(LL, id[i], -point(LL, id[i]) + val[i] * (ll)id[i]);
            }
        }
        else {
            int l, r, m; cin >> l >> r >> m;

            ll sss;
            if (m == 1) sss = sum(SS, l, r);
            else {
                ll lenM = r - l + 1 - m;
                ll h = (r - l + 1) - m + 1;

                sss = (ll)h * sum(SS, l, r);
                sss -= f(l + m, r);
                sss -=  sum(SS, l, l + lenM - 1) * h - f(l, l + lenM - 1);
            }

            cout << sss << endl;
        }
    }

}

/*
Array bounds *
long long vs int
Garbage value
Sometimes, VNOI views "arrays out of bounds" as "wrong answer"
*/

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