Submission #547816

#	Time	Username	Problem	Language	Result	Execution time	Memory
547816		ValiAntonie	Addk (eJOI21_addk)	C++14	100 / 100	161 ms	8700 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int n,k,q,i,j,st,dr,m,lungime,indici[15];
long long v[100001],sum,suma1[100001],suma2[100001],suma3[100001],x,sum1,sum2,sum3,nr,element,j2,element2,nr2;

void update1(int x, long long y){
for(j=x;j<=n;j+=(j&-j)){
    suma1[j] += y;
}
}

long long sumaa1(int x){
    sum1 = 0;
    for(j=x;j>=1;j-=(j&-j)){
        sum1 += suma1[j];
    }
    return sum1;
}

void update2(int x, long long y){
for(j=x;j<=n;j+=(j&-j)){
    suma2[j] += y;
}
}

long long sumaa2(int x){
    sum2 = 0;
    for(j=x;j>=1;j-=(j&-j)){
        sum2 += suma2[j];
    }
    return sum2;
}

void update3(int x, long long y){
for(j=x;j<=n;j+=(j&-j)){
    suma3[j] += y;
}
}

long long sumaa3(int x){
    sum3 = 0;
    for(j=x;j>=1;j-=(j&-j)){
        sum3 += suma3[j];
    }
    return sum3;
}



int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>k;
for(i=1;i<=n;i++){
    cin>>x;
    v[i] = x;
    update1(i,x);
    update2(i,i*x);
    update3(i,(n - i + 1) * x);
}
cin>>q;
for(i=1;i<=q;i++){
    cin>>x;
    if(x == 1){
        for(j2=1;j2<=k;j2++){
          cin>>indici[j2];
        }
        nr = sumaa1(indici[1]) - sumaa1(indici[1]-1);
        nr2 = sumaa1(indici[k]) - sumaa1(indici[k]-1);
        for(j2=1;j2<=k-1;j2++){
            element = sumaa1(indici[j2+1]) - sumaa1(indici[j2+1]-1);
            element2 = sumaa1(indici[j2]) - sumaa1(indici[j2]-1);
            update1(indici[j2],-element2);
            update1(indici[j2],element);
            update2(indici[j2],-indici[j2]*element2);
            update2(indici[j2],indici[j2]*element);
            update3(indici[j2],-(n-indici[j2]+1)*element2);
            update3(indici[j2],(n-indici[j2]+1)*element);
        }
        update1(indici[k],-nr2);
        update1(indici[k],nr);
        update2(indici[k],-indici[k]*nr2);
        update2(indici[k],indici[k]*nr);
        update3(indici[k],-(n-indici[k]+1)*nr2);
        update3(indici[k],(n-indici[k]+1)*nr);
    }
    else{
        cin>>st>>dr>>m;
        sum = 0;
        lungime = dr - st + 1;
        sum += sumaa2(st + m - 2) - sumaa2(st-1) - ((st - 1) * (sumaa1(st + m - 2) - sumaa1(st-1)));
        sum = sum + sumaa3(dr) - sumaa3(dr-m+1) - ((n - dr) * (sumaa1(dr) - sumaa1(dr-m+1)));
        sum += m * (sumaa1(dr-m+1) - sumaa1(st+m-2));
        cout << sum << '\n';
    }
}
    return 0;
}

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