oj.uz

Submission #477719

# Submission time Handle Problem Language Result Execution time Memory
477719 2021-10-03T10:22:13 Z chungdinh Addk (eJOI21_addk) C++14
100 / 100
 405 ms 5680 KB 
#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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 4 ms 3404 KB Output is correct
3 Correct 7 ms 3404 KB Output is correct
4 Correct 10 ms 3488 KB Output is correct
5 Correct 13 ms 3496 KB Output is correct
6 Correct 15 ms 3532 KB Output is correct
7 Correct 19 ms 3520 KB Output is correct
8 Correct 23 ms 3516 KB Output is correct
9 Correct 29 ms 3588 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3780 KB Output is correct
2 Correct 93 ms 4048 KB Output is correct
3 Correct 121 ms 4264 KB Output is correct
4 Correct 211 ms 4912 KB Output is correct
5 Correct 296 ms 5640 KB Output is correct
6 Correct 279 ms 5444 KB Output is correct
7 Correct 271 ms 5444 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 4184 KB Output is correct
2 Correct 272 ms 5016 KB Output is correct
3 Correct 405 ms 4916 KB Output is correct
4 Correct 334 ms 5680 KB Output is correct