Submission #1072287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072287		vjudge1	Addk (eJOI21_addk)	C++17	0 / 100	86 ms	4432 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nn "\n";
#define pb push_back
const int N = 5e6 + 8  , inf = 1e9+7 ;
int  n , m , q  , k , a[N] , t[N] , p[N] ,s[N];
void build(int v , int l , int r ){
    if( l == r ){
        t[v] = a[l];
        p[v] = a[l]*l  , s[v] = a[l]*(n - l + 1 );
        return;
    }
    int mid = ( l + r )>>1;
    build(v * 2 ,  l , mid );
    build(v * 2 + 1 , mid + 1, r );
    p[v] = p[v*2]+p[v*2+1];
    s[v] = s[v*2]+s[v*2+1];
    t[v] = t[v*2]+t[v*2+1];
}
int gett(int v , int tl , int tr , int l , int r ){
    if(tl <= l && r <= tr ){
        return t[v];
    }
    if(l > tr || r < tl ){
        return 0 ;
    }
    int mid = ( l + r )/2;
    return gett(v * 2 ,tl , tr , l , mid )+gett(v* 2 + 1 , tl , tr , mid + 1 , r );
}
int getp(int v , int tl , int tr , int l , int r ){
    if(tl <= l && r <= tr ){
        return p[v];
    }
    if(l > tr || r < tl ){
        return 0 ;
    }
    int mid = ( l + r )/2;
    return getp(v * 2 ,tl , tr , l , mid )+getp(v* 2 + 1 , tl , tr , mid + 1 , r );
}
int gets(int v , int tl , int tr , int l , int r ){
    if(tl <= l && r <= tr ){
        return s[v];
    }
    if(l > tr || r < tl ){
        return 0 ;
    }
    int mid = ( l + r )/2;
    return gets(v * 2 ,tl , tr , l , mid )+gets(v* 2 + 1 , tl , tr , mid + 1 , r );
}
void up(int v, int pos , int l , int r , int x ){
    if(l == r ){
        t[v] = x  , p[v] = x * l , s[v] = x * ( n - l +1);
        return ;
    }
    int mid = ( l + r )/2;
    if(pos <= mid ){
        up(v * 2 , pos , l , mid , x );
    }
    else {
        up(v * 2 + 1 , pos , mid + 1 , r , x );
    }
    p[v] = p[v*2]+p[v*2+1];
    s[v] = s[v*2]+s[v*2+1];
    t[v] = t[v*2]+t[v*2+1];
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin>> n >> k ;
    for(int i= 1  ; i <= n; i++){
        cin>> a[i];
    }
    build(1 , 1 , n );
    cin>> q ;
    while(q--) {
        int h;
        cin >> h;
        if (h == 1) {
            vector<int> v;
            int w[k + 1];
            for (int i = 1; i <= k; i++) {
                cin >> w[i];
                v.pb(a[w[i]]);
            }
            v.pb(a[v[0]]);
            v.erase(v.begin());
            for (int i = 1; i <= k; i++) {
                a[w[i]] = v[i - 1];
                up(1, w[i], 1, n, v[i - 1]);
            }
        } else {
            int l, r;
            cin >> l >> r >> m;
            m = min(m, (r - l + 1) - m + 1);
            int pos2 = l + m - 1;
            int pos3 = r - m + 1;
            int l1 = min(pos2, pos3);
            int r1 = max(pos2, pos3);
            int a1 = getp(1, l, l1 - 1 , 1, n) + (gett(1, l, l1-1, 1, n) * (-(l - 1)));
            int b2 = gett(1, l1, r1, 1, n) * m;
            int c2 = gets(1, r1 + 1, r, 1, n) + ((gett(1, r1 + 1, r, 1, n) * (-(r - r1 - 1 ))));
            cout << b2 +a1 + c2 << nn
        }
    }
}

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