Submission #832195

#	Time	Username	Problem	Language	Result	Execution time	Memory
832195		exodus_	Addk (eJOI21_addk)	C++14	0 / 100	2084 ms	2004 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int nmax = 1e5+5;
int A[nmax];
long long pref[nmax];
long long segtree[4*nmax];
void build(int idx, int low, int high) {
    if(low==high) {
        segtree[idx] = A[low];
        return;
    }
    int mid = (low+high)/2;
    build(2*idx, low, mid);
    build(2*idx+1, mid+1, high);
    segtree[idx] = segtree[2*idx]+segtree[2*idx+1];
}
long long query(int idx, int low, int high, int l, int r) {
    if(low>=l && high<=r) {
        return segtree[idx];
    }
    if(low>r || high<l) {
        return 0;
    }
    int mid = (low+high)/2;
    long long left = query(2*idx,low,mid,l,r);
    long long right = query(2*idx+1,mid+1,high,l,r);
    return left+right;
}
int main() {
    int N,K,Q;
    cin >> N >> K;
    pref[0] = 0;
    for(int i=1; i<=N; i++) {
        cin >> A[i];
        pref[i] = A[i]+pref[i-1];
    }
    build(1,1,N);
    cin >> Q;
    int com,l,r,m;
    long long sum;
    for(int i=1; i<=Q; i++) {
        cin >> com;
        sum = 0;
        if(com==1) {
            cin >> m;
        } else {
            cin >> l >> r >> m;
            for(int i=l; i<=r; i++) {
                if(i+m-1 <= r) {
                    sum+=query(1,1,N,i,i+m-1);
                }
            }
            cout << sum << endl;
        }
    }
    return 0;
}

• Subtask 1: 0 / 36
• Subtask 2: 0 / 56
• Subtask 3: 0 / 8