Submission #621262

#	Time	Username	Problem	Language	Result	Execution time	Memory
621262		Mer123haba456	Addk (eJOI21_addk)	C++14	92 / 100	170 ms	8328 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long double ld;
#define N lli(2e6)
#define MOD lli(1e9 + 7)
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0);
#define heps(v) v.begin(),v.end()
typedef vector<lli> vlli;
typedef pair<lli,lli> plli;
typedef pair<lli,plli> pplli;
typedef vector<plli> vplli;
typedef vector<pplli> vpplli;
typedef map<lli,lli> mlli;

lli t,n,m,k;

string str;

vlli vect;

lli prefart[N];

lli pref[N];

lli sufart[N];

lli suf[N];

int main(){
    fast_io
    cin >> n >> k;
    for(lli i = 0;i<n;i++){
        cin >> t;
        vect.push_back(t);
    }
    for(lli i = 1;i<=n;i++){
        pref[i] = pref[i-1] + vect[i-1];
        prefart[i] = prefart[i-1] + vect[i-1] * i;
    }
    for(lli i = n-1;i>=0;i--){
        suf[i] = suf[i+1] + vect[i];
        sufart[i] = sufart[i+1] + vect[i] * (n - i);
    }
    cin >> t;
    while(t--){
        lli l,r,q;
        cin >> m;
        if(m == 1){
            for(lli i = 0;i<k;i++){
                cin >> q;
            }
        }else{
            cin >> l >> r >> q;
            lli yuk = 2 * q -2;
            lli bas = 0, son = 0;
            lli fa = r - l + 1;
            lli cev = 0;
            if(yuk <= fa){
                bas = q-1;
                son = q-1;
                cev += q * (pref[r-q + 1] - pref[l + q-2]);
            }else{
                lli ort = fa - q + 1;
                cev += ort * (pref[r-ort + 1] - pref[l + ort-2]);
                bas = ort-1;
                son = ort -1;
            }
            bas--;son--;
            lli bsay = 0, ssay = 0;
            if(bas >= 0)
                bsay = (prefart[l + bas] - prefart[l-1]) - (l-1) * (pref[l + bas] - pref[l-1]);
            if(son >= 0)
                ssay = (sufart[r - son -1] - sufart[r]) - (n - r) * (suf[r - son - 1] - suf[r]);
            cev += bsay + ssay;
            //cout << bsay << " " << ssay << endl;
            cout << cev << endl;
        }
    }
}

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