Submission #1042317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042317		vjudge1	Addk (eJOI21_addk)	C++17	0 / 100	62 ms	4140 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int tree[100000*4];
vector<int> vec;

void build(int node,int l,int r)
{
    if(l==r)
    {
        tree[node]=vec[l-1];

    }
    else
    {
        int m=(l+r)/2;
        build(node*2,l,m);
        build(node*2+1,m+1,r);
    }

}

void upd(int node,int i,int x,int l ,int r)
{
    if(l==r)
    {
        tree[node]=x;
    }
    else
    {
        int m=(l+r)/2;
        if(i<=m)
        {
            upd(node*2,i,x,l,m);
        }
        else
            upd(node*2+1,i,x,m+1,r);
    }
}

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


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,k;
    cin>>n>>k;
    for(int n1=n;n1>0;n1--)
    {
        int x;
        cin>>x;
        vec.push_back(x);
    }
    build(1,1,vec.size());
    pair<int,int> sqd[n]={},sqd2[n];
    int val=0,val2=0;
    for(int i=0;i<n;i++)
    {
        val=val+vec[i]*(i%317+1);
        val2+=vec[i];
        if(i%317==316)
        {
            sqd[i]={val,val2};
            val=0;
            val2=0;
        }
    }
    val=0,val2=0;
    for(int i=n-1;i>=0;i--)
    {
        val=val+vec[i]*((vec.size()-i-1)%317+1);
        val2+=vec[i];
        if((vec.size()-i-1)%317==316)
        {
            sqd2[i]={val,val2};
            val=0;
            val2=0;
        }
    }
    int q;
    cin>>q;
    for(;q>0;q--)
    {
        int x;
        cin>>x;
        if(x==1)
        {
            vector<int> temp;
            for(int k1=k;k1>0;k1--)
            {
                int br;
                cin>>br;
                temp.push_back(br-1);
            }
            int tempp=vec[temp[0]];
            for(int i=0;i<temp.size();i++)
            {
                if(i==temp.size()-1)
                {
                int br2=316-(temp[i]%317);
                if(temp[i]+br2<n)
                {
                    sqd[temp[i]+br2].first-=(vec[temp[i]]*(temp[i]%317+1));
                    sqd[temp[i]+br2].second-=(vec[temp[i]]);
                vec[temp[i]]=tempp;
                sqd[temp[i]+br2].first+=(vec[temp[i]]*(temp[i]%317+1));
                sqd[temp[i]+br2].second+=(vec[temp[i]]);


                }
                else
                    vec[temp[i]]=tempp;

                    br2=316-((vec.size()-temp[i]-1)%317);

                    if(temp[i]-br2>=0)
                {
                    sqd[temp[i]-br2].first-=(vec[temp[i]]*(temp[i]%317+1));
                    sqd[temp[i]-br2].second-=(vec[temp[i]]);
                vec[temp[i]]=tempp;
                sqd[temp[i]-br2].first+=(vec[temp[i]]*(temp[i]%317+1));
                sqd[temp[i]-br2].second+=(vec[temp[i]]);


                }
                else
                    vec[temp[i]]=tempp;


                upd(1,temp[i]+1,tempp,1,vec.size());
                }
                else
                {
                    int br=temp[i+1];
                int br2=316-(temp[i]%317);
                if(temp[i]+br2<n)
                {
                    sqd[temp[i]+br2].first-=(vec[temp[i]]*(temp[i]%317+1));
                    sqd[temp[i]+br2].second-=(vec[temp[i]]);
            vec[temp[i]]=vec[br];
                    sqd[temp[i]+br2].second+=(vec[temp[i]]);
                sqd[temp[i]+br2].second+=(vec[temp[i]]);

                }
                else
                    vec[temp[i]]=vec[br];

                                        br2=316-((vec.size()-temp[i]-1)%317);

                           if(temp[i]-br2>=0)
                {
                    sqd[temp[i]-br2].first-=(vec[temp[i]]*(temp[i]%317+1));
                    sqd[temp[i]-br2].second-=(vec[temp[i]]);
            vec[temp[i]]=vec[br];
                    sqd[temp[i]-br2].second+=(vec[temp[i]]);
                sqd[temp[i]-br2].second+=(vec[temp[i]]);

                }
                else
                    vec[temp[i]]=vec[br];


                upd(1,temp[i]+1,vec[br],1,vec.size());
                }

            }
        }
        else
        {
            int l,r,m;
            cin>>l>>r>>m;
            int sz=r-l+1;
            if(m>sz/2)
            {
                m=sz-m+1;
            }
            int l1=l+m-1,r1=r-m+1;
            int res=0;
            if(l1>r1)
                swap(l1,r1);
            if(l1<=r1)
            {
                res=res+sum(1,1,vec.size(),l1,r1)*m;
            }

            for(int m1=m-1,l2=l1-2;l2>=l-1;l2--,m1--)
            {
                if(l2%317==316 && l2-316>=l-1)
                {
                    res=res+sqd[l2].first+(sqd[l2].second*(m1-317));
                    m1-=316;
                    l2-=316;
                }
                else
                {
                    res+=vec[l2]*m1;
                }

            }
            l1=r1;
            for(int m1=m-1;l1<=r-1;l1++,m1--)
            {
                if((vec.size()-l1-1)%317==316 && l1+316<=r-1)
                {
                    res=res+sqd[l1].first+(sqd[l1].second*(m1-317));
                    m1+=316;
                    l1+=316;
                }
                else
                {
                    res+=vec[l1]*m1;
                }
            }
            cout<<res<<"\n";
        }

    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:115:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             for(int i=0;i<temp.size();i++)
      |                         ~^~~~~~~~~~~~
Main.cpp:117:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |                 if(i==temp.size()-1)
      |                    ~^~~~~~~~~~~~~~~
Main.cpp:130:17: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  130 |                 else
      |                 ^~~~
Main.cpp:133:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  133 |                     br2=316-((vec.size()-temp[i]-1)%317);
      |                     ^~~

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