Submission #1128366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128366		12345678	Addk (eJOI21_addk)	C++20	64 / 100	327 ms	8820 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

#define ll long long

ll n, q, k, a[nx], t, l, r, m, upd[nx];

struct segtree
{
    ll d[4*nx];
    void update(int l, int r, int i, int idx, ll vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=vl, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    ll query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql||r<l) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
} up, dn, sm;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>a[i], up.update(1, n, 1, i, i*a[i]), dn.update(1, n, 1, i, (n-i+1)*a[i]), sm.update(1, n ,1, i, a[i]);
    //for (int i=1; i<=n; i++) cout<<"debug "<<i<<' '<<sm.query(1, n, 1, i, i)<<' '<<up.query(1, n,1 , i, i)<<'\n';
    cin>>q;
    while (q--)
    {
        cin>>t;
        if (t==1)
        {
            for (int i=1; i<=k; i++) cin>>upd[i];
            int tmp=a[upd[1]];
            for (int i=1; i<k; i++) a[upd[i]]=a[upd[i+1]];
            a[upd[k]]=tmp;
            for (int i=1; i<=k; i++) up.update(1, n, 1, upd[i], upd[i]*a[upd[i]]), dn.update(1, n, 1, upd[i], (n-upd[i]+1)*a[upd[i]]), sm.update(1, n ,1, upd[i], a[upd[i]]);
            //for (int i=1; i<=n; i++) cout<<"debug "<<i<<' '<<sm.query(1, n, 1, i, i)<<' '<<up.query(1, n,1 , i, i)<<'\n';
        }
        else
        {
            cin>>l>>r>>m;
            int mx=min(m, (r-l+1)-m+1);
            ll lft=up.query(1, n, 1, l, l+mx-1)-sm.query(1, n, 1, l, l+mx-1)*(l-1);
            ll md=mx*sm.query(1, n, 1, l+mx, r-mx);
            ll rgt=dn.query(1, n, 1, r-mx+1, r)-sm.query(1, n, 1, r-mx+1, r)*(n-r);
            //cout<<mx<<' '<<lft<<' '<<md<<' '<<rgt<<'\n';
            cout<<lft+md+rgt<<'\n';
        }
    }
}

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