Submission #830258

#	Time	Username	Problem	Language	Result	Execution time	Memory
830258		andecaandeci	Addk (eJOI21_addk)	C++17	92 / 100	1004 ms	5108 KiB

Main

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int nx = 1e5 + 5;

int n, k;
ll a[nx];


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        a[i] += a[i-1];
    }
    int q, type, dummy;
    cin>>q;
    while(q--){
        cin >> type;
        if(type == 1){
            for(int i=1; i<=k; i++) cin >> dummy;
        }
        else{
            ll ret = 0;
            int l, r, m;
            cin >> l >> r >> m;
            int top = min(m, r-l+1-m+1);

            for(int i=1; i<=top; i++){
                ret += (a[r] - a[l-1]);
                --r;
                ++l;
            }
            cout << ret <<'\n';
        }
    }
    

    return 0;
}


/*

if k = 1;
query 1 doesn't change anything
focus on query type 2 only:
notice it only take prefix sum

7 2 5 1 9 3 4 6
  ^ ^ ^ ^
    ^     ^ 
      ^     ^
2 2 7 4

top = min(m-1, r-l+1-m+1)

*/

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