oj.uz

Submission #595053

# Submission time Handle Problem Language Result Execution time Memory
595053 2022-07-13T09:54:13 Z Urvuk3 Addk (eJOI21_addk) C++17
100 / 100
 244 ms 14224 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll INF=1e9,LINF=1e18,MOD=1e9+7; const ll MAXN=1e5+1;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define PRINT(x) cerr<<#x<<'-'<<x<<endl<<flush;
#define pb push_back
#define PRINTvec(x) { cerr<<#x<<"-"; for(int i=0;i<sz(x);i++) cerr<<x[i]<<" "; cerr<<endl; }

struct Node{
    ll s,pref,suf,d;
}seg[4*MAXN];

vector<int> a;

Node Merge(Node n1,Node n2){
    Node ret;
    if(n1.d==0) ret=n2;
    else if(n2.d==0) ret=n1;
    else{
        ret.s=n1.s+n2.s;
        ret.d=n1.d+n2.d;
        ret.pref=n1.pref+(n2.d*n1.s+n2.pref);
        ret.suf=n2.suf+(n1.d*n2.s+n1.suf);
    }
    return ret;
}

void Init(int node,int l,int r){
    if(l==r){
        seg[node].s=a[l];
        seg[node].pref=a[l];
        seg[node].suf=a[l];
        seg[node].d=1;
        return;
    }
    Init(2*node,l,mid); Init(2*node+1,mid+1,r);
    seg[node]=Merge(seg[2*node],seg[2*node+1]);
}

void Update(int node,int l,int r,int idx,int val){
    if(l==r){
        a[idx]=val;
        seg[node].s=val;
        seg[node].pref=val;
        seg[node].suf=val;
        seg[node].d=1;
        return;
    }
    if(idx<=mid) Update(2*node,l,mid,idx,val);
    else Update(2*node+1,mid+1,r,idx,val);
    seg[node]=Merge(seg[2*node],seg[2*node+1]);
}

Node Query(int node,int l,int r,int L,int R){
    Node ret; ret.s=ret.pref=ret.suf=ret.d=0;
    if(R<L) return ret;
    if(L<=l && r<=R){
        return seg[node];
    }
    if(L<=mid) ret=Merge(ret,Query(2*node,l,mid,L,R));
    if(R>mid) ret=Merge(ret,Query(2*node+1,mid+1,r,L,R));
    return ret;
}

void Solve(){
    int N,K; cin>>N>>K; a.resize(N+1);
    for(int i=1;i<=N;i++) cin>>a[i];
    Init(1,1,N);
    int Q; cin>>Q;
    while(Q--){
        int tip; cin>>tip;
        if(tip==2){
            int L,R,M;
            cin>>L>>R>>M;
            int cnt=(R-L+1)-(M-1);
            ll pref=Query(1,1,N,L,L+cnt-2).pref;
            ll suf=Query(1,1,N,R-cnt+2,R).suf;
            ll sum=Query(1,1,N,L,R).s;
            cout<<sum*cnt-pref-suf<<endl;
        }
        else{
            vector<int> idx1(K),idx2(K);
            for(int i=0;i<K;i++) cin>>idx1[i];
            idx2[K-1]=idx1[0];
            for(int i=K-2;i>=0;i--){
                idx2[i]=idx1[i+1];
            }
            vector<int> vals;
            for(int i=0;i<K;i++) vals.pb(a[idx2[i]]);
            for(int i=0;i<K;i++){
                Update(1,1,N,idx1[i],vals[i]);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        Solve();
    }
    return 0;
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 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 896 KB Output is correct
7 Correct 9 ms 852 KB Output is correct
8 Correct 8 ms 852 KB Output is correct
9 Correct 12 ms 1480 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2900 KB Output is correct
2 Correct 40 ms 3628 KB Output is correct
3 Correct 55 ms 6092 KB Output is correct
4 Correct 111 ms 11532 KB Output is correct
5 Correct 161 ms 12856 KB Output is correct
6 Correct 149 ms 12672 KB Output is correct
7 Correct 159 ms 12620 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 6436 KB Output is correct
2 Correct 143 ms 12312 KB Output is correct
3 Correct 244 ms 14224 KB Output is correct
4 Correct 201 ms 13080 KB Output is correct