oj.uz

Submission #650411

# Submission time Handle Problem Language Result Execution time Memory
650411 2022-10-13T16:58:42 Z sofija6 Addk (eJOI21_addk) C++14
100 / 100
 247 ms 14548 KB 
#include <bits/stdc++.h>
#define ll long long
#define MAXN 100010
using namespace std;
ll n,a[MAXN],m,p[20],v[20];
struct element
{
    ll s=0,sl=0,sr=0,cnt=0;
};
struct seg_tree
{
    vector<element> st;
    element neutral_element;
    element Merge(element x,element y)
    {
        element z;
        z.s=x.s+y.s;
        z.sl=x.sl+y.sl+y.s*x.cnt;
        z.sr=y.sr+x.sr+x.s*y.cnt;
        z.cnt=x.cnt+y.cnt;
        return z;
    }
    void Init()
    {
        m=1;
        while (m<n)
            m <<= 1;
        st.resize(2*m,neutral_element);
    }
    void Build()
    {
        for (ll i=m;i<m+n;i++)
            st[i]={a[i-m+1],a[i-m+1],a[i-m+1],1};
        for (ll i=m-1;i>0;i--)
            st[i]=Merge(st[2*i],st[2*i+1]);
    }
    void Add(ll pos,ll val,ll x,ll lx,ll rx)
    {
        if (rx<pos || lx>pos)
            return;
        if (rx==lx)
        {
            st[x]={val,val,val,1};
            return;
        }
        ll mid=(lx+rx)/2;
        if (pos<=mid)
            Add(pos,val,2*x,lx,mid);
        else
            Add(pos,val,2*x+1,mid+1,rx);
        st[x]=Merge(st[2*x],st[2*x+1]);
    }
    element Calc(ll l,ll r,ll x,ll lx,ll rx)
    {
        if (rx<l || lx>r)
            return neutral_element;
        if (lx>=l && rx<=r)
            return st[x];
        ll mid=(lx+rx)/2;
        return Merge(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
    }
};
seg_tree S;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll k,q,t;
    cin >> n >> k;
    for (ll i=1;i<=n;i++)
        cin >> a[i];
    S.Init();
    S.Build();
    cin >> q;
    while (q--)
    {
        cin >> t;
        if (t==1)
        {
            for (ll i=1;i<=k;i++)
            {
                cin >> p[i];
                v[i]=a[p[i]];
            }
            for (ll i=1;i<k;i++)
            {
                a[p[i]]=v[i+1];
                S.Add(p[i],v[i+1],1,1,m);
            }
            a[p[k]]=v[1];
            S.Add(p[k],v[1],1,1,m);
            continue;
        }
        ll l,r,len;
        cin >> l >> r >> len;
        ll x,y,z;
        if (r-l+1>=2*len)
        {
            x=S.Calc(l,l+len-1,1,1,m).sl;
            y=len*S.Calc(l+len,r-len,1,1,m).s;
            z=S.Calc(r-len+1,r,1,1,m).sr;
        }
        else
        {
            ll d=r-l+1-len;
            x=S.Calc(l,l+d-1,1,1,m).sl;
            y=(d+1)*S.Calc(l+d,r-d,1,1,m).s;
            z=S.Calc(r-d+1,r,1,1,m).sr;
        }
        cout << x+y+z << "\n";
    }
    return 0;
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 7 ms 724 KB Output is correct
6 Correct 7 ms 984 KB Output is correct
7 Correct 9 ms 1108 KB Output is correct
8 Correct 9 ms 1108 KB Output is correct
9 Correct 16 ms 1748 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2760 KB Output is correct
2 Correct 48 ms 3740 KB Output is correct
3 Correct 75 ms 6184 KB Output is correct
4 Correct 118 ms 11864 KB Output is correct
5 Correct 178 ms 13236 KB Output is correct
6 Correct 178 ms 12944 KB Output is correct
7 Correct 182 ms 13032 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 5220 KB Output is correct
2 Correct 175 ms 12644 KB Output is correct
3 Correct 247 ms 14548 KB Output is correct
4 Correct 211 ms 13520 KB Output is correct