oj.uz

Submission #832015

# Submission time Handle Problem Language Result Execution time Memory
832015 2023-08-20T20:13:18 Z AlphaMale06 Addk (eJOI21_addk) C++14
100 / 100
 79 ms 11068 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
const int N = 100005;

int fenw[N][3];
int a[N];

int Get1(int ind, int t){
    int sum=0;
    int indx=ind;
    while(indx>0){
        sum+=fenw[indx][t];
        indx-=(indx&-indx);
    }
    return sum;
}

int Getind(int l, int r, int ind){
    return Get1(r, ind)- Get1(l-1, ind);
}


int Get(int l, int r, int m, int n){
    int len=r-l+1;
    if(m>(len+1)/2){
        m=len-m+1;
    }
    int h=m;
    if(h==1)return Getind(l, r, 0);
    return Getind(l, l+h-1, 1)+Getind(l+h, r-h+1, 0)*h+Getind(r-h+2, r, 2)-Getind(l, l+h-1, 0)*(l-1)-Getind(r-h+2, r, 0)*(n-r);
}

void Upd(int ind, int val1, int val2, int val3){
    int indx=ind;
    while(indx<N){
        fenw[indx][0]+=val1;
        fenw[indx][1]+=val2;
        fenw[indx][2]+=val3;
        indx+=(indx&-indx);
    }
}

void Update(int n, int pisa){
    int ind[n];
    int c[n];
    for(int i=0; i< n; i++){
        cin >> ind[i];
        c[i]=a[ind[i]-1];
    }
    int d[n];
    int b[n];
    b[n-1]=ind[0];
    for(int i=0; i<n-1; i++){
        b[i]=ind[i+1];
    }
    for(int i=0; i< n; i++){
        d[i]=a[b[i]-1];
    }
    for(int i=0; i< n; i++){
        a[ind[i]-1]=d[i];
    }
    for(int i=0; i< n; i++){
        Upd(ind[i], d[i]-c[i], (d[i]-c[i])*ind[i], (d[i]-c[i])*(pisa-ind[i]+1));
    }
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i=0; i< n; i++){
        cin >> a[i];
    }
    int pref[n+1][3];
    pref[0][0]=0; pref[0][1]=0;
    for(int i=1; i<=n; i++){
        pref[i][0]=pref[i-1][0]+a[i-1];
        pref[i][1]=pref[i-1][1]+i*a[i-1];
    }
    pref[n][2]=a[n-1];
    for(int i=1; i<=n; i++){
        pref[i][2]=pref[i-1][2]+a[i-1]*(n-i+1);
    }
    fenw[0][0]=fenw[0][1]=fenw[0][2]=0;
    for(int i=1; i<=n; i++){
        fenw[i][0]=pref[i][0];
        fenw[i][0]-=pref[i-(i&-i)][0];
        fenw[i][1]=pref[i][1];
        fenw[i][1]-=pref[i-(i&-i)][1];
        fenw[i][2]=pref[i][2];
        fenw[i][2]-=pref[i-(i&-i)][2];
    }
    int q;
    cin >> q;
    while(q--){
        int t;
        cin >> t;
        if(t==1){
            Update(k, n);
        }
        else{
            int l, r, m;
            cin >> l >> r >> m;
            cout << Get(l, r, m, n) << '\n';
        }
    }
}

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 1 ms 508 KB Output is correct
4 Correct 2 ms 528 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 3 ms 720 KB Output is correct
7 Correct 3 ms 832 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 5 ms 1236 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2000 KB Output is correct
2 Correct 19 ms 3028 KB Output is correct
3 Correct 20 ms 4072 KB Output is correct
4 Correct 36 ms 6948 KB Output is correct
5 Correct 52 ms 9720 KB Output is correct
6 Correct 48 ms 9420 KB Output is correct
7 Correct 51 ms 9472 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5424 KB Output is correct
2 Correct 49 ms 8172 KB Output is correct
3 Correct 79 ms 11068 KB Output is correct
4 Correct 58 ms 10024 KB Output is correct