Submission #520415

#	Time	Username	Problem	Language	Result	Execution time	Memory
520415		Alex_tz307	Addk (eJOI21_addk)	C++17	100 / 100	137 ms	8312 KiB

Main

#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 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8