Submission #1263696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263696		mkkkkkkkk	Addk (eJOI21_addk)	C++20	92 / 100	240 ms	6908 KiB

Main

#include <bits/stdc++.h>

using namespace std;

long long tree[2][400000];
vector<long long> vec;

void build(long long node,long long l,long long r)
{
    if(l==r)
    {
            tree[0][node]=vec[l];
            tree[1][node]=vec[l]*(l+1);
    }
    else
    {
        long long m=(l+r)/2;
        build(node*2+1,l,m);
        build(node*2+2,m+1,r);
        tree[0][node]=tree[0][node*2+1]+tree[0][node*2+2];
        tree[1][node]=tree[1][node*2+1]+tree[1][node*2+2];
    }
}

long long query(long long node,long long l,long long r,long long L,long long R,long long t)
{
    if(l>=L && r<=R)
    {
        return tree[t][node];
    }
    else if(l>R || L>r)
    {
        return 0;
    }
    else
    {
        long long m=(l+r)/2;
        return query(node*2+1,l,m,L,R,t)+query(node*2+2,m+1,r,L,R,t);
    }
}




int main()
{
    long long n,k;
    cin>>n>>k;
    for(long long n1=n;n1>0;n1--)
    {
        long long x;
        cin>>x;
        vec.push_back(x);
    }
    long long q;
    cin>>q;
    build(0,0,vec.size()-1);
    for(;q>0;q--)
    {
        long long t;
        cin>>t;
        if(t==1)
        {
            for(long long k1=k;k1>0;k1--)
            {
                long long x;
                cin>>x;
            }

        }
        else
        {
            long long l,r,m;
            cin>>l>>r>>m;
            l--;
            r--;
            if((r-l+1)<2*m)
            {
                m=(r-l+2)-m;
            }
            long long br=0;
            if(m!=1)
            {
                br=br+query(0,0,vec.size()-1,l,l+m-2,1);


                    br=br-query(0,0,vec.size()-1,l,l+m-2,0)*(l);



                    br=br+query(0,0,vec.size()-1,r-m+2,r,0)*(r+2);

                br=br-query(0,0,vec.size()-1,r-m+2,r,1);


            }
            br=br+query(0,0,vec.size()-1,l+m-1,r-m+1,0)*(m);
            cout<<br<<endl;

        }
    }
    return 0;
}

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