Submission #1253624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253624		matthew	Addk (eJOI21_addk)	C++20	0 / 100	16 ms	1860 KiB

Main

#include <stdio.h>
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 sz = r - l + 1;

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

  return left_sum + mid_sum + right_sum;
}

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++) {
    pos_aib.update(i, 1LL * i * a[i]);
    aib.update(i, a[i]);
    rpos_aib.update(i, 1LL * (n + 1 - i) * a[i]);
  }

  int q;
  scanf("%d", &q);
  for(int i = 0; i < q; i++) {
    int type;
    scanf("%d", &type);
    if(type == 1) {
      ;
    } 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:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d%d", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~
Main.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
Main.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d", &type);
      |     ~~~~~^~~~~~~~~~~~~
Main.cpp:75:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |       scanf("%d%d%d", &l, &r, &m);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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