답안 #593517

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
593517 2022-07-11T10:13:46 Z serkanrashid Addk (eJOI21_addk) C++14
100 / 100
354 ms 12584 KB
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int maxn=1e5+5;
int n,k,q;
long long a[maxn],b[maxn],pref[4*maxn],suff[4*maxn],tree[4*maxn];
long long ql,qr,val;

void make_tree(int v, int l, int r)
{
    if(l==r)
    {
        pref[v]=a[r]*r;
        suff[v]=a[r]*(n-r+1);
        tree[v]=a[r];
        return;
    }
    int mid=(l+r)/2;
    make_tree(v*2+0,l,mid+0);
    make_tree(v*2+1,mid+1,r);
    pref[v]=pref[v*2]+pref[v*2+1];
    suff[v]=suff[v*2]+suff[v*2+1];
    tree[v]=tree[v*2]+tree[v*2+1];
}

void update(int v, int l, int r)
{
    if(l>qr||r<ql||l>r) return;
    if(l>=ql&&r<=qr)
    {
        pref[v]=val*r;
        suff[v]=val*(n-r+1);
        tree[v]=val;
        return;
    }
    int mid=(l+r)/2;
    update(v*2+0,l,mid+0);
    update(v*2+1,mid+1,r);
    pref[v]=pref[v*2]+pref[v*2+1];
    suff[v]=suff[v*2]+suff[v*2+1];
    tree[v]=tree[v*2]+tree[v*2+1];
}

long long query_pref(int v, int l, int r)
{
    if(l>qr||r<ql||l>r) return 0;
    if(l>=ql&&r<=qr) return pref[v];
    int mid=(l+r)/2;
    return query_pref(v*2+0,l,mid+0) + query_pref(v*2+1,mid+1,r);
}

long long query_suff(int v, int l, int r)
{
    if(l>qr||r<ql||l>r) return 0;
    if(l>=ql&&r<=qr) return suff[v];
    int mid=(l+r)/2;
    return query_suff(v*2+0,l,mid+0) + query_suff(v*2+1,mid+1,r);
}

long long query_tree(int v, int l, int r)
{
    if(l>qr||r<ql||l>r) return 0;
    if(l>=ql&&r<=qr) return tree[v];
    int mid=(l+r)/2;
    return query_tree(v*2+0,l,mid+0) + query_tree(v*2+1,mid+1,r);
}

void read()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    make_tree(1,1,n);
    cin >> q;
    int ch,l,r,m,idx,mid,obr;
    long long ans=0;
    for(int i=1;i<=q;i++)
    {
        cin >> ch;
        ans=0;
        if(ch==1)
        {
            for(int j=1;j<=k;j++)
            {
                cin >> b[j];
            }
            long long pom_val=0;
            ql=b[1];
            qr=b[1];
            pom_val=query_tree(1,1,n);
            for(int j=1;j<k;j++)
            {
                ql=b[j+1];
                qr=b[j+1];
                val=query_tree(1,1,n);
                ql=b[j];
                qr=b[j];
                update(1,1,n);
            }
            val=pom_val;
            ql=b[k];
            qr=b[k];
            update(1,1,n);
        }
        else
        {
            cin >> l >> r >> m;
            m=min(m,r-l+2-m);
            idx=l+m-1;
            mid=(l+r)/2;
            idx=min(idx,mid);
            m=idx-l+1;
            ql=l;
            qr=idx-1;
            ans+=query_pref(1,1,n);
            ans-=query_tree(1,1,n)*(l-1);
            obr=l+r-idx;
            ql=obr+1;
            qr=r;
            ans+=query_suff(1,1,n);
            ans-=query_tree(1,1,n)*(n-r);
            ql=idx;
            qr=obr;
            ans+=query_tree(1,1,n)*(idx-l+1);
            cout << ans << endl;
        }
    }
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	read();
return 0;
}

/*
8 1
7 2 5 1 9 3 4 6
6
2 3 8 4
2 5 6 2
2 6 8 1
2 1 8 4
2 1 8 6
2 3 7 2
*/

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 9 ms 836 KB Output is correct
7 Correct 10 ms 852 KB Output is correct
8 Correct 11 ms 852 KB Output is correct
9 Correct 15 ms 1236 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 2296 KB Output is correct
2 Correct 52 ms 2540 KB Output is correct
3 Correct 69 ms 4196 KB Output is correct
4 Correct 129 ms 8096 KB Output is correct
5 Correct 214 ms 8692 KB Output is correct
6 Correct 184 ms 8596 KB Output is correct
7 Correct 176 ms 8604 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 4224 KB Output is correct
2 Correct 203 ms 10808 KB Output is correct
3 Correct 354 ms 12584 KB Output is correct
4 Correct 249 ms 11480 KB Output is correct