oj.uz

Submission #832194

# Submission time Handle Problem Language Result Execution time Memory
832194 2023-08-21T06:12:16 Z exodus_ Addk (eJOI21_addk) C++14
0 / 100
 2000 ms 1920 KB 
#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;
    int left = query(2*idx,low,mid,l,r);
    int 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 48 ms 340 KB Output is correct
3 Correct 216 ms 380 KB Output is correct
4 Correct 481 ms 428 KB Output is correct
5 Correct 851 ms 460 KB Output is correct
6 Incorrect 1393 ms 544 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 56.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 1200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 1920 KB Time limit exceeded
2 Halted 0 ms 0 KB -