Submission #774824

# Submission time Handle Problem Language Result Execution time Memory
774824 2023-07-06T03:50:49 Z vjudge12 Addk (eJOI21_addk) C++17
100 / 100
1214 ms 4904 KB
#include<bits/stdc++.h>
using namespace std;
long long a[100001];
long long st[400001];
void build(long long no,long long l,long long r)
{
    if(l==r)
    {
        st[no]=a[l];
        return;
    }
    long long mid=(l+r)/2;
    build(no*2,l,mid);
    build(no*2+1,mid+1,r);
    st[no]=st[no*2+1]+st[no*2];
    return;
}

void pointupd(long long no,long long l,long long r,long long ep,long long x)
{
    if(l>ep||r<ep)
        return;
    if(l==r)
    {
        st[no]=x;
        return;
    }
    long long mid=(l+r)/2;
    pointupd(no*2,l,mid,ep,x);
    pointupd(no*2+1,mid+1,r,ep,x);
    st[no]=st[no*2+1]+st[no*2];
    return;
}

long long sum(long long no,long long l,long long r,long long el,long long er)
{
    if(l>er||r<el)
        return 0;
    if(l>=el&&r<=er)
        return st[no];
    long long mid=(l+r)/2;
    return sum(no*2+1,mid+1,r,el,er)+sum(no*2,l,mid,el,er);
}

long long qr[11];
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    long long n,q,k,qrt,l,r,m;
    cin>>n>>k;
    for(long long i=1; i<=n; ++i)
    {
        cin>>a[i];
    }
    cin>>q;
    build(1,1,n);
    for(long long i=0; i<q; ++i)
    {
        cin>>qrt;
        if(qrt==1)
        {
            for(long long j=0; j<k; ++j)
            {
                cin>>qr[j];
            }
            long long kkl=a[qr[0]];
            for(long long j=0; j<k-1; ++j)
            {
                a[qr[j]]=a[qr[j+1]];
                pointupd(1,1,n,qr[j],a[qr[j]]);
            }
            a[qr[k-1]]=kkl;
            pointupd(1,1,n,qr[k-1],a[qr[k-1]]);
        }
        if(qrt==2)
        {
            cin>>l>>r>>m;
            long long ans=0;
            long long rr=r,ll=l;
            long long k=sum(1,1,n,ll,rr);
            for(long long i=0;i<m;++i)
            {
                ans+=k;
                k-=a[ll];
                k-=a[rr];
                ++ll;
                --rr;
                if(ll>rr||rr<l+m-1)
                {
                    break;
                }
            }
            cout<<ans<<"\n";
        }
    }
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 8 ms 584 KB Output is correct
8 Correct 10 ms 544 KB Output is correct
9 Correct 19 ms 704 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 63 ms 1240 KB Output is correct
2 Correct 137 ms 1384 KB Output is correct
3 Correct 241 ms 2260 KB Output is correct
4 Correct 744 ms 3916 KB Output is correct
5 Correct 1214 ms 4712 KB Output is correct
6 Correct 1086 ms 4508 KB Output is correct
7 Correct 922 ms 4420 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 202 ms 2216 KB Output is correct
2 Correct 758 ms 4368 KB Output is correct
3 Correct 204 ms 4112 KB Output is correct
4 Correct 1208 ms 4904 KB Output is correct