Submission #1263703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263703		mkkkkkkkk	Addk (eJOI21_addk)	C++20	0 / 100	142 ms	3484 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);
    }
}

void upd(int node,int i,int x,int l,int r)
{
    if(l==r)
    {
        tree[0][node]=x;
        tree[1][node]=x*(l+1);
    }
    else
    {
        int m=(l+r)/2;
        if(i<=m)
            upd(node*2+1,i,x,l,m);
        else
            upd(node*2+2,i,x,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];
    }
}




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)
        {
            vector<int> vecc;
            for(long long k1=k;k1>0;k1--)
            {
                long long x;
                cin>>x;
                vecc.push_back(x-1);
            }
            for(int i=1;i<vecc.size();i++)
            {
                upd(0,vecc[i-1],vec[vecc[i]],0,vec.size()-1);
            }
            upd(0,vecc[vecc.size()-1],vec[vecc[0]],0,vec.size()-1);
            int temp=vec[vecc[0]];
            for(int i=0;i<vecc.size()-1;i++)
            {
                vec[vecc[i]]=vec[vecc[i+1]];
            }
            vec[vecc[vecc.size()-1]]=temp;


        }
        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: 0 / 36
• Subtask 2: 0 / 56
• Subtask 3: 0 / 8