oj.uz

Submission #1035393

# Submission time Handle Problem Language Result Execution time Memory
1035393 2024-07-26T10:12:22 Z makanhulia Addk (eJOI21_addk) C++17
100 / 100
 374 ms 15700 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,k;
int a[100001];
vector<pair<int,pair<int,int> > > st;

void build(int idx,int l,int r){
    if(l==r){
        st[idx].first=a[l];
        st[idx].second.first=l*a[l];
        st[idx].second.second=(n-l+1)*a[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*idx,l,mid);
    build(2*idx+1,mid+1,r);
    st[idx].first=st[2*idx].first+st[2*idx+1].first;
    st[idx].second.first=st[2*idx].second.first+st[2*idx+1].second.first;
    st[idx].second.second=st[2*idx].second.second+st[2*idx+1].second.second;
}

void update(int idx,int l,int r,int pos,int val){
    if(l==r){
        st[idx].first=val;
        st[idx].second.first=l*val;
        st[idx].second.second=(n-l+1)*val;
        return ;
    }
    int mid=(l+r)/2;
    if(pos<=mid){
        update(2*idx,l,mid,pos,val);
    }
    else{
        update(2*idx+1,mid+1,r,pos,val);
    }
    st[idx].first=st[2*idx].first+st[2*idx+1].first;
    st[idx].second.first=st[2*idx].second.first+st[2*idx+1].second.first;
    st[idx].second.second=st[2*idx].second.second+st[2*idx+1].second.second;

}

pair<int,pair<int,int> > query(int idx,int l,int r,int posl,int posr){
    if(l>posr|| r<posl)return {0,{0,0}};
    if(l>=posl && r<=posr) return st[idx];
    int mid=(l+r)/2;
    pair<int,pair<int,int> >e=query(2*idx,l,mid,posl,posr);
    pair<int,pair<int,int> >b=query(2*idx+1,mid+1,r,posl,posr);
    return {e.first+b.first,{e.second.first+b.second.first,e.second.second+b.second.second}};
}

signed main(){
    cin>>n>>k;
    st=vector<pair<int,pair<int,int> > >(4*n+1);

    for(int q=1;q<=n;q++){
        cin>>a[q];
    }
    build(1,1,n);

    int u;
    cin>>u;
    while(u--){
        int type;
        cin>>type;
        if(type==1){
            int val[k+1];
            int idx[k+1];
            for(int q=1;q<=k;q++){
                cin>>idx[q];
                val[q]=query(1,1,n,idx[q],idx[q]).first;
            }
            for(int q=1;q<k;q++){
                update(1,1,n,idx[q],val[q+1]);
            }
            update(1,1,n,idx[k],val[1]);
        }
        else{
            int l,r,m;
            cin>>l>>r>>m;
            int seg=(r-l+1-m+1);
            m=min(seg,m);

            int posl=l+m-1;
            int posr=r-m+1;
            //cout<<posl<<" "<<posr<<endl;
            pair<int,pair<int,int> > awal=query(1,1,n,l,posl-1);
            pair<int,pair<int,int> > tngh=query(1,1,n,posl,posr);
            pair<int,pair<int,int> > akh=query(1,1,n,posr+1,r);

            int ans=awal.second.first-awal.first*(l-1);
            ans+=tngh.first * m;
            ans+=akh.second.second-akh.first*(n-r);
            cout<<ans<<endl;   
        }
    }
    

}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 4 ms 864 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 10 ms 956 KB Output is correct
6 Correct 10 ms 1112 KB Output is correct
7 Correct 13 ms 1216 KB Output is correct
8 Correct 15 ms 1356 KB Output is correct
9 Correct 21 ms 1804 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3224 KB Output is correct
2 Correct 68 ms 4432 KB Output is correct
3 Correct 128 ms 6052 KB Output is correct
4 Correct 165 ms 10164 KB Output is correct
5 Correct 250 ms 14416 KB Output is correct
6 Correct 257 ms 14288 KB Output is correct
7 Correct 259 ms 14288 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 7764 KB Output is correct
2 Correct 245 ms 11860 KB Output is correct
3 Correct 374 ms 15700 KB Output is correct
4 Correct 300 ms 14804 KB Output is correct