Submission #1036395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036395		kebine	Addk (eJOI21_addk)	C++17	92 / 100	61 ms	7444 KiB

Main

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 1e5;

int n, k, q, a[maxn+5], pref[maxn+5], pos[15], pre[maxn+5], suf[maxn+5];

signed 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];
  }
  pref[0] = pre[0] = suf[n+1] = 0;
  for (int i=1; i<=n; i++) {
    pref[i] = pref[i-1] + a[i];
    pre[i] = pre[i-1] + a[i] * i;
    suf[n-i+1] = suf[n-i+2] + a[n-i+1] * i;
  }
  cin >> q;
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      for (int i=1; i<=k; i++) {
        cin >> pos[i];
      }
      continue; // subtask 1, 2
    }
    else {
      int l, r, m;
      cin >> l >> r >> m;
      int len = r - l + 1;
      int h = min(len-m+1, m);
      int x = l + h - 1, y = r - h + 1;
      int ans = (h*(pref[y] - pref[x-1]))  +  (pre[x-1]-pre[l-1]-(l-1)*(pref[x-1]-pref[l-1]))  +  (suf[y+1]-suf[r+1]-(n-r)*(pref[r]-pref[y]));
//      cout << "len: " << len << " x: " << x << " y: " << y << " h: " << h << "\n";
      cout << ans << "\n";
    }
  }
}

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