Submission #1031536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031536		AndiR	Addk (eJOI21_addk)	C++14	100 / 100	73 ms	8272 KiB

Main

// Author: Tanasescu Andrei-Rares
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#include <cassert>

#pragma GCC optimize("O3")

#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;

ifstream fin ("addk.in");
ofstream fout ("addk.out");

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll Nmax=1e5+5, inf=1e9+5, Kmax=10;

int n, q, k, cer, l, r, m;
int w[Nmax], perm[Kmax], neww[Kmax];

struct AIB{
    ll v[Nmax];

    inline ll _sum(int pos){
        ll sum=0;
        while (pos>0){
            sum+=v[pos];
            pos-=pos&-pos;
        }
        return sum;
    }
    inline ll sum(int l, int r){
        return _sum(r)-_sum(l-1);
    }
    inline void update(int pos, ll val){
        while (pos<=n){
            v[pos]+=val;
            pos+=pos&-pos;
        }
    }
    inline void build(bool lin, bool cresc){
        for (int i=1; i<=n; i++){
            if (lin)
                if (cresc)
                    v[i]+=(ll)i*w[i];
                else v[i]+=(ll)(n-i+1)*w[i];
            else v[i]+=w[i];

            int j=i+(i&-i);
            if (j<=n)
                v[j]+=v[i];
        }
    }
}aiblinc, aiblind, aibdel;

inline void permutate(){
    for (int i=0; i<k; i++){
        int ind=perm[i];
        int nxtind=perm[(i+1)%k];
        ll delta=w[nxtind]-w[ind];

        aiblinc.update(ind, delta*ind);
        aiblind.update(ind, delta*(n-ind+1));
        aibdel.update(ind, delta);

        neww[i]=w[nxtind];
    }
    for (int i=0; i<k; i++)
        w[perm[i]]=neww[i];
}
inline ll calculate(){
    int d=r-l+1;
    if (m>d/2)
        m=d-m+1;
    ll sum=0;
    sum+=aiblinc.sum(l, l+m-1)-aibdel.sum(l, l+m-1)*(l-1);
    sum+=aiblind.sum(r-m+1, r)-aibdel.sum(r-m+1, r)*(n-r);
    if (d%2==1 && m==d/2+1)
        sum-=(ll)w[l+m-1]*m;
    else sum+=aibdel.sum(l+m, r-m)*m;

    return sum;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k;
    for (int i=1; i<=n; i++)
        cin>>w[i];

    aiblinc.build(1, 1);
    aiblind.build(1, 0);
    aibdel.build(0, 0);

    cin>>q;
    while (q--){
        cin>>cer;
        if (cer==1){
            for (int i=0; i<k; i++)
                cin>>perm[i];
            permutate();
        }
        else{
            cin>>l>>r>>m;
            cout<<calculate()<<'\n';
        }
    }

    return 0;
}

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