oj.uz

Submission #843709

# Submission time Handle Problem Language Result Execution time Memory
843709 2023-09-04T12:59:40 Z Andrijanikolic73 Addk (eJOI21_addk) C++17
92 / 100
 213 ms 6760 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int t[2*N];
int query(int i){int ans=0;for(;i>0;i-=i&-i)ans+=t[i];return ans;}
void update(int i,int v){for(;i<N;i+=i&-i)t[i]+=v;}
int query(int l,int r){
    if(l>r)return 0;
    if(l==0)return query(r);
    return query(r)-query(l-1);
}
signed main(){
    int n,k;
    cin>>n>>k;
    int a[n+1];
    for(int i=1;i<=n;i++)cin>>a[i];
    int pref[n+1];
    pref[0]=0;
    for(int i=1;i<=n;i++)pref[i]=pref[i-1]+a[i];
    int q;
    cin>>q;
    if(max(n,q)<=10000&&k==1){
        while(q--){
            int o;
            cin>>o;
            if(o==1){
                int X;
                cin>>X;
                continue;
            }
            int l,r,m;
            cin>>l>>r>>m;
            int ans=0;
            // i>r-m+1
            //for(int i=l;i<=r-m+1;i++)ans+=pref[i+m-1]-pref[i-1];.
            for(int i=r;i>=l+m-1;i--){
                ans+=pref[i];
            }
            for(int i=l-1;i<=r-m;i++)ans-=pref[i];
            cout<<ans;
            cout<<endl;
        }
        return 0;
    }
    if(k==1){
        for(int i=1;i<=n;i++)update(i,pref[i]);
        while(q--){
            int o;
            cin>>o;
            if(o==1){
                int X;
                cin>>X;
                continue;
            }
            int l,r,m;
            cin>>l>>r>>m;
            int ans=query(l+m-1,r);
            ans-=query(l-1,r-m);
            cout<<ans;
            cout<<endl;
        }
    }
}
/*
8 1
7 2 5 1 9 3 4 6
1
2 2 7 4
*/

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 7 ms 348 KB Output is correct
4 Correct 9 ms 348 KB Output is correct
5 Correct 13 ms 348 KB Output is correct
6 Correct 18 ms 348 KB Output is correct
7 Correct 23 ms 412 KB Output is correct
8 Correct 29 ms 576 KB Output is correct
9 Correct 51 ms 600 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1116 KB Output is correct
2 Correct 61 ms 2136 KB Output is correct
3 Correct 82 ms 2896 KB Output is correct
4 Correct 150 ms 4696 KB Output is correct
5 Correct 213 ms 6760 KB Output is correct
6 Correct 194 ms 6428 KB Output is correct
7 Correct 192 ms 6428 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1076 KB Output isn't correct
2 Halted 0 ms 0 KB -