oj.uz

Submission #520415

# Submission time Handle Problem Language Result Execution time Memory
520415 2022-01-29T21:59:02 Z Alex_tz307 Addk (eJOI21_addk) C++17
100 / 100
 137 ms 8312 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;
const int MAXK = 10;
int n, k, a[MAXN], v[MAXK];
int64_t sum[MAXN], pref[MAXN], suf[MAXN];

void update_sum(int poz, int64_t x) {
  for (int i = poz; i <= n; i += i & -i)
    sum[i] += x;
}

int64_t query_sum(int x) {
  int64_t ans = 0;
  for (int i = x; i > 0; i -= i & -i)
    ans += sum[i];
  return ans;
}

int64_t interval_sum(int l, int r) {
  return query_sum(r) - query_sum(l - 1);
}

void update_pref(int poz, int64_t x) {
  for (int i = poz; i <= n; i += i & -i)
    pref[i] += x;
}

int64_t query_pref(int x) {
  int64_t ans = 0;
  for (int i = x; i > 0; i -= i & -i)
    ans += pref[i];
  return ans;
}

int64_t interval_pref(int l, int r) {
  return query_pref(r) - query_pref(l - 1);
}

void update_suf(int poz, int64_t x) {
  poz = n - poz + 1;
  for (int i = poz; i <= n; i += i & -i)
    suf[i] += x;
}

int64_t query_suf(int x) {
  x = n - x + 1;
  int64_t ans = 0;
  for (int i = x; i > 0; i -= i & -i)
    ans += suf[i];
  return ans;
}

int64_t interval_suf(int l, int r) {
  return query_suf(l) - query_suf(r + 1);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    update_sum(i, a[i]);
    update_pref(i, (int64_t)i * a[i]);
    update_suf(i, (int64_t)(n - i + 1) * a[i]);
  }
  int q;
  cin >> q;
  for (int _q = 0; _q < q; ++_q) {
    int t;
    cin >> t;
    if (t == 1) {
      for (int i = 0; i < k; ++i) {
        cin >> v[i];
        int x = v[i];
        update_sum(x, -a[x]);
        update_pref(x, (int64_t)-x * a[x]);
        update_suf(x, (int64_t)-(n - x + 1) * a[x]);
      }
      int aux = a[v[0]];
      for (int i = 0; i < k - 1; ++i)
        a[v[i]] = a[v[i + 1]];
      a[v[k - 1]] = aux;
      for (int i = 0; i < k; ++i) {
        int x = v[i];
        update_sum(v[i], a[x]);
        update_pref(v[i], (int64_t)x * a[x]);
        update_suf(v[i], (int64_t)(n - x + 1) * a[x]);
      }
      continue;
    }
    int l, r, m;
    cin >> l >> r >> m;
    if ((m << 1) > r - l + 1)
      m = r - l + 2 - m;
    int64_t ans = interval_pref(l, l + m - 1) - interval_sum(l, l + m - 1) * (l - 1);
    ans += interval_suf(r - m + 1, r) - interval_sum(r - m + 1, r) * (n - r);
    if ((m << 1) == r - l + 2)
      ans -= (int64_t)m * a[(l + r) >> 1];
    else ans += interval_sum(l + m, r - m) * m;
    cout << ans << '\n';
  }
  return 0;
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 4 ms 644 KB Output is correct
8 Correct 4 ms 716 KB Output is correct
9 Correct 7 ms 972 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1592 KB Output is correct
2 Correct 20 ms 2180 KB Output is correct
3 Correct 29 ms 2884 KB Output is correct
4 Correct 48 ms 4928 KB Output is correct
5 Correct 61 ms 7044 KB Output is correct
6 Correct 59 ms 6764 KB Output is correct
7 Correct 69 ms 6724 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 4092 KB Output is correct
2 Correct 68 ms 6000 KB Output is correct
3 Correct 137 ms 8312 KB Output is correct
4 Correct 79 ms 7236 KB Output is correct