oj.uz

답안 #1016220

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1016220 2024-07-07T14:09:56 Z AndrijaM Addk (eJOI21_addk) C++14
92 / 100
 122 ms 9044 KB 
#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>=1;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)
            {
                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
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 7 ms 860 KB Output is correct
8 Correct 9 ms 1024 KB Output is correct
9 Correct 13 ms 1116 KB Output is correct

Subtask #2
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 1624 KB Output is correct
2 Correct 39 ms 2972 KB Output is correct
3 Correct 47 ms 3788 KB Output is correct
4 Correct 88 ms 6480 KB Output is correct
5 Correct 122 ms 9044 KB Output is correct
6 Correct 112 ms 8996 KB Output is correct
7 Correct 117 ms 8800 KB Output is correct

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 3152 KB Output isn't correct
2 Halted 0 ms 0 KB -