Submission #1016213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016213		AndrijaM	Xor Sort (eJOI20_xorsort)	C++14	0 / 100	1 ms	348 KiB

xorsort

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int logn=25;

/* LazySeg tree
int n;
int st[4*maxn];///min
int lz[4*maxn];


void u(int L,int R,int i,int j,int nval,int pos)
{
    if(lz[pos]!=0)
    {
        st[pos]+=lz[pos];
        if(L!=R)
        {
            lz[2*pos]+=lz[pos];
            lz[2*pos+1]+=lz[pos];
        }
        lz[pos]=0;
    }
    if(i<=L && R<=j)
    {
        st[pos]+=nval;
        if(L!=R)
        {
            lz[2*pos]+=nval;
            lz[2*pos+1]+=nval;
        }
        return ;
    }
    if(R<i || L>j)
    {
        return;
    }
    int mid=(L+R)/2;
    u(L,mid,i,j,nval,2*pos);
    u(mid+1,R,i,j,nval,2*pos+1);
    st[pos]=min(st[2*pos],st[2*pos+1]);
}

int query(int L,int R,int i,int j,int pos)
{
    if(lz[pos]!=0)
    {
        st[pos]+=lz[pos];
        if(L!=R)
        {
            lz[2*pos]+=lz[pos];
            lz[2*pos+1]+=lz[pos];
        }
        lz[pos]=0;
    }
    if(i<=L && R<=j)
    {
        return st[pos];
    }
    if(R<i || L>j)
    {
        return 1e15;
    }
    int mid=(L+R)/2;
    return min(query(L,mid,i,j,2*pos),query(mid+1,R,i,j,2*pos+1));
}*/

signed main()
{
    ///freopen("sirbun.in","r",stdin);
    ///freopen("sirbun.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    int x[n+1];
    int p[n+1];
    p[0]=0;
    int prefL[n+1];
    prefL[0]=0;
    int A[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>x[i];
        p[i]=p[i-1]+x[i];
        A[i]=x[i]*i;
        prefL[i]=prefL[i-1]+A[i];
    }
    int prefR[n+2];
    prefR[n+1]=0;
    int B[n+1];
    int cnt=1;
    for(int i=n;i>=0;i--)
    {
        B[i]=x[i]*cnt;
        prefR[i]=prefR[i+1]+B[i];
        cnt++;
    }
    int q;
    cin>>q;
    while(q--)
    {
        int t,l,r,m;
        cin>>t;
        if(t==1)
        {
            for(int i=0;i<k;i++)
            {
                int num;
                cin>>num;
            }
            continue;
        }
        cin>>l>>r>>m;
        int len=r-l+1;
        int ans=0;
        if(len==m || m==1)
        {
            ans+=p[r]-p[l-1];
            cout<<ans<<endl;
            continue;
        }
        if(len-2*(m-1)>=0)
        {
            int M=m-1;
            int kr=l-1;
            int l2=l+M-1;
            ans+=prefL[l2]-prefL[l-1];
            ans-=(p[l2]-p[l-1])*kr;
            int r2=r-M+1;
            kr=n-r;
            ans+=prefR[r2]-prefR[r+1];
            ans-=(p[r]-p[r2-1])*kr;
            ans+=(p[r2-1]-p[l2])*m;
        }
        else
        {
            int kol=len-2*(m-1);
            m+=(kol-1);
            int kr=l-1;
            int l2=l+m-1;
            ans+=prefL[l2]-prefL[l-1];
            ans-=(p[l2]-p[l-1])*kr;
            int r2=r-m+1;
            kr=n-r;
            ans+=prefR[r2]-prefR[r+1];
            ans-=(p[r]-p[r2-1])*kr;
            ans+=(p[r2-1]-p[l2])*m;
        }
        cout<<ans<<endl;
    }
    return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40