oj.uz

Submission #602531

# Submission time Handle Problem Language Result Execution time Memory
602531 2022-07-23T07:36:11 Z berr Addk (eJOI21_addk) C++17
92 / 100
 158 ms 8676 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[1000005], st[1000005*4], b[1000005], c[1000005], n, k;

void build(int v, int l, int r)
{
    if(l==r) st[v]=a[l];
    else
    {
        build(v*2, l, (l+r)/2); 
        build(v*2+1, (l+r)/2+1, r);

        st[v]=st[v*2]+st[v*2+1];    
    }
}

int get(int v, int tl, int tr, int l, int r)
{
    if(l>tr||r<tl) return 0;
    else if(l>=tl&&r<=tr) return st[v];
    else
    {
        int mid=(l+r)/2;
        return get(v*2, tl, tr, l, mid)+get(v*2+1, tl, tr, mid+1, r);
    }
}

int dec(int l, int r)
{
    if(l>r) return 0;
    if(l==0) return b[r];
    else
    {

        return b[r]-b[l-1]-((l)*get(1, l, r, 0, n-1));
    }
}

int dec2(int l, int r)
{
    if(l>r) return 0;
    if(r==n-1) return c[l];
    else
    {
        return c[l]-c[r+1]-((n-r-1)*get(1, l, r, 0, n-1));
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin>>n>>k;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }

    build(1, 0, n-1);

    b[0]=a[0];
    for(int i=1; i<n; i++)
    {
        b[i]=(i+1)*a[i]+b[i-1];
    }
    c[n-1]=a[n-1];
    for(int i=n-2; i>=0; i--)
    {
        c[i]=(n-i)*a[i]+c[i+1];
    }
    int q; cin>>q;

    while(q--)
    {
        int type; cin>>type;
        if(type==1)
        {
            for(int i=0, x; i<k; i++) cin>>x;
        }
        else
        {
            int l, r, m; cin>>l>>r>>m;
            l--; r--;
            int ans=get(1, l, r, 0, n-1)*m;
            ans-=dec2(l, l+m-2);
            ans-=dec(r-m+2, r);
            cout<<ans<<"\n";
        }
    }
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 6 ms 724 KB Output is correct
7 Correct 6 ms 804 KB Output is correct
8 Correct 11 ms 844 KB Output is correct
9 Correct 15 ms 1108 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2148 KB Output is correct
2 Correct 34 ms 2672 KB Output is correct
3 Correct 53 ms 3940 KB Output is correct
4 Correct 87 ms 6744 KB Output is correct
5 Correct 137 ms 8676 KB Output is correct
6 Correct 129 ms 8452 KB Output is correct
7 Correct 158 ms 8436 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 4944 KB Output isn't correct
2 Halted 0 ms 0 KB -