Submission #666465

#	Time	Username	Problem	Language	Result	Execution time	Memory
666465		divad	Addk (eJOI21_addk)	C++14	100 / 100	333 ms	9508 KiB

Main

#include <iostream>
#include <cstring>
#define int long long
#define MAX 100002
using namespace std;
int n,k,a[MAX],asc[MAX],desc[MAX],v[MAX],x,t,m,l,r,q,c[MAX],cpy[MAX];

int query(int aib[MAX], int pos){
    int ans = 0;
    for(int i = pos; i > 0; i -= (i&-i)){
        ans += aib[i];
    }
    return ans;
}

void update(int aib[MAX], int pos, int val){
    for(int i = pos; i <= n; i += (i&-i)){
        aib[i] += val;
    }
}

int range(int aib[MAX], int x, int y){
    return query(aib, y)-query(aib, x-1);
}

signed main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
        cpy[i] = v[i];
        update(a, i, v[i]);
        update(asc, i, i*v[i]);
        update(desc, i, (n-i+1)*v[i]);
    }
    cin >> q;
    while(q--){
        cin >> t;
        if(t == 2){
            cin >> l >> r >> m;
            int len = r-l+1;
            if(m > len/2){
                m = len-m+1;
            }
            /// asc   - [l      , l+m-2  ]
            /// const - [l+m-1  , r-(m-1)]
            /// desc  - [r-(m-2), r      ]
            /// S1  = range(asc, l, l+m-2) - (l-1)*range(a, l, l+m-2)
            /// S2  = m * range(a, l+m-1, r-(m-1))
            /// S3  = range(desc, r-(m-2), r) - ( (r-(m-2))-(m-1) ) * range(a, r-(m-2), r)
            int s1 = range(asc, l, l+m-2) - (l-1)*range(a, l, l+m-2);
            int s2 = m * range(a, l+m-1, r-(m-1));
            int s3 = range(desc, r-(m-2), r) - ((n-(r-(m-2))+1)-(m-1)) * range(a, r-(m-2), r);
            cout << s1+s2+s3 << "\n";
        }else{
            for(int i = 1; i <= k; i++){
                cin >> c[i];
            }
            int cpval = v[c[1]];
            for(int i = 2; i <= k; i++){
                int prev_val = v[c[i-1]];
                v[c[i-1]] = v[c[i]];
            }
            v[c[k]] = cpval;
            for(int i = 1; i <= k; i++){
                int dif = v[c[i]]-cpy[c[i]];
                update(a, c[i], dif);
                dif = c[i]*v[c[i]] - c[i]*cpy[c[i]];
                update(asc, c[i], dif);
                dif = (n-c[i]+1)*v[c[i]] - (n-c[i]+1)*cpy[c[i]];
                update(desc, c[i], dif);
                cpy[c[i]] = v[c[i]];
            }
        }
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:61:21: warning: unused variable 'prev_val' [-Wunused-variable]
   61 |                 int prev_val = v[c[i-1]];
      |                     ^~~~~~~~

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