Submission #1189191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189191		zadniprovska	Addk (eJOI21_addk)	C++20	92 / 100	28 ms	5004 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define el '\n'
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<long long, long long>
#define ppll pair< long long, pair<long long, long long> >
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()

const ll DIM = 1e6+7;
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ll maxlog = 20;

ll a[DIM], b[DIM], c[DIM], s[DIM];

void solve() {

    ll n, k;
    cin >> n >> k;

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

        s[i] = s[i-1]+a[i];

        b[i] = b[i-1] + i*a[i];
        c[i] = (n-i+1)*a[i];

        //add1(i, a[i]);
        //add2(i, b[i]);
    }

    for (int i=n; i>=1; i--) {
        c[i] += c[i+1];
    }

    /*for (int i=1; i<=n; i++) {
        cout << s[i] << " ";
    }
    cout << el;
    for (int i=1; i<=n; i++) {
        cout << b[i] << " ";
    }
    cout << el;
    for (int i=1; i<=n; i++) {
        cout << c[i] << " ";
    }
    cout << el;*/

    ll nq;
    cin >> nq;
    for (int i=1; i<=nq; i++) {

        ll type;
        cin >> type;

        if (type == 1) {
            ll t;
            for (int i=1; i<=k; i++) {
                cin >> t;
            }
        }

        else {
            ll L, R, m;
            cin >> L >> R >> m;

            ll len = R - L + 1;
            if (len >= 2*(m-1)) {

                ll res = b[L+m-2] - b[L-1] - (L-1)*(s[L+m-2] - s[L-1]);

                res += c[R-m+2] - c[R+1] - (n-R)*(s[R] - s[R-m+1]);

                res += m*(s[R-m+1] - s[L+m-2]);

                cout << res << el;

            }
            else {
                ll m1 = len - m + 1;

                ll res = b[L+m1-2] - b[L-1] - (L-1)*(s[L+m1-2] - s[L-1]);

                res += c[R-m1+2] - c[R+1] - (n-R)*(s[R] - s[R-m1+1]);

                res += m1*(s[R-m1+1] - s[L+m1-2]);

                cout << res << el;
            }




        }



    }




}



signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    //freopen("nocross.in", "r", stdin);
    //freopen("nocross.out", "w", stdout);

    int ntest = 1;
    //cin >> ntest;
    while (ntest--){
        solve();
    }
    return 0;

}
;

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