Submission #1253644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253644		matthew	Addk (eJOI21_addk)	C++20	92 / 100	46 ms	4472 KiB

Main

#include <stdio.h>
#include <vector>
#include <algorithm>
using ll = long long;

const int MAX_N = 100'000;

struct AIB {
  int n;
  ll aib[MAX_N + 1];

  void init(int _n) {
    n = _n;
  };

  void update(int pos, ll delta) {
    for(; pos <= n; pos += pos & -pos) {
      aib[pos] += delta;
    }
  }

  ll query(int pos) {
    ll ret = 0;
    for(; pos > 0; pos &= pos - 1) {
      ret += aib[pos];
    }
    return ret;
  }

  ll range_query(int l, int r) {
    return query(r) - query(l - 1);
  }
};

int n;
int a[MAX_N + 1];
AIB pos_aib, aib, rpos_aib;

ll query_mid(int l, int r, int mid) {
  int mid_left = l + mid - 1;
  int mid_right = r - mid + 1;

  ll left_sum = pos_aib.range_query(l, mid_left - 1)
          - (l - 1) * aib.range_query(l, mid_left - 1);
  ll mid_sum = mid * aib.range_query(mid_left, mid_right);
  ll right_sum = rpos_aib.range_query(mid_right + 1, r)
          - (n - r) * aib.range_query(mid_right + 1, r);

  return left_sum + mid_sum + right_sum;
}

void update(int pos, int new_val, int old_val) {
  int delta = new_val - old_val;
  pos_aib.update(pos, 1LL * pos * delta);
  aib.update(pos, delta);
  rpos_aib.update(pos, 1LL * (n + 1 - pos) * delta);
}

int main() {
  int k;
  scanf("%d%d", &n, &k);
  for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }

  pos_aib.init(n);
  aib.init(n);
  rpos_aib.init(n);

  for(int i = 1; i <= n; i++) {
    update(i, a[i], 0);
  }

  int q;
  scanf("%d", &q);
  for(int i = 0; i < q; i++) {
    int type;
    scanf("%d", &type);
    if(type == 1) {
      std::vector<int> pos;
      for(int j = 0; j < k; j++) {
        int p;
        scanf("%d", &p);
        pos.push_back(p);
      }
      std::sort(pos.begin(), pos.end());
      int first = a[pos[0]];
      for(int i = 0; i < (int)pos.size() - 1; i++) {
        update(pos[i], a[pos[i + 1]], a[pos[i]]);
      }
      int last_pos = pos[(int)pos.size() - 1];
      update(last_pos, first, a[last_pos]);
    } else {
      int l, r, m;
      scanf("%d%d%d", &l, &r, &m);
      int sz = r - l + 1;
      if(sz < m) {
        printf("0\n");
      } else if(sz >= 2 * m - 1) {
        printf("%lld\n", query_mid(l, r, m));
      } else {
        printf("%lld\n", query_mid(l, r, sz - m + 1));
      }
    }
  }

  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d%d", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~
Main.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
Main.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d", &type);
      |     ~~~~~^~~~~~~~~~~~~
Main.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%d", &p);
      |         ~~~~~^~~~~~~~~~
Main.cpp:95:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |       scanf("%d%d%d", &l, &r, &m);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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