oj.uz

Submission #1036395

# Submission time Handle Problem Language Result Execution time Memory
1036395 2024-07-27T10:31:47 Z kebine Addk (eJOI21_addk) C++17
92 / 100
 61 ms 7444 KB 
#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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 536 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1628 KB Output is correct
2 Correct 10 ms 2396 KB Output is correct
3 Correct 25 ms 3156 KB Output is correct
4 Correct 22 ms 5212 KB Output is correct
5 Correct 61 ms 7444 KB Output is correct
6 Correct 30 ms 7248 KB Output is correct
7 Correct 31 ms 7248 KB Output is correct

Subtask #3
0 / 8.0

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