Submission #832015

#	Time	Username	Problem	Language	Result	Execution time	Memory
832015		AlphaMale06	Addk (eJOI21_addk)	C++14	100 / 100	79 ms	11068 KiB

Main

#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 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8