Submission #1253635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253635		matthew	Addk (eJOI21_addk)	C++20	0 / 100	17 ms	2116 KiB

Main

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

#define int ll

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) {
    if(l > r) return 0;
    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;
}

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

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