oj.uz

Submission #547816

# Submission time Handle Problem Language Result Execution time Memory
547816 2022-04-11T19:50:39 Z ValiAntonie Addk (eJOI21_addk) C++14
100 / 100
 161 ms 8700 KB 
#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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 5 ms 752 KB Output is correct
8 Correct 5 ms 724 KB Output is correct
9 Correct 6 ms 980 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1736 KB Output is correct
2 Correct 18 ms 2388 KB Output is correct
3 Correct 26 ms 3100 KB Output is correct
4 Correct 55 ms 5296 KB Output is correct
5 Correct 65 ms 7392 KB Output is correct
6 Correct 66 ms 7248 KB Output is correct
7 Correct 65 ms 7080 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 4284 KB Output is correct
2 Correct 65 ms 6348 KB Output is correct
3 Correct 161 ms 8700 KB Output is correct
4 Correct 75 ms 7632 KB Output is correct