Submission #1209080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209080		TraianDanciu	Addk (eJOI21_addk)	C++20	100 / 100	256 ms	6516 KiB

Main

#include <iostream>

using namespace std;

const int MAXN = 100000;
const int MAXK = 10;

int v[MAXN + 1], poz[MAXK + 1], new_values[MAXK + 1];

struct SegmentTree {
  struct Node {
    long long sum, lazy;
  } tree[4 * (MAXN + 1)];
  int n;

  void init(int n) {
    this->n = n;
  }

  void propagate(int node, int left, int right) {
    int middle = (left + right) / 2;
    tree[2 * node].sum += tree[node].lazy * (middle - left + 1);
    tree[2 * node].lazy += tree[node].lazy;
    tree[2 * node + 1].sum += tree[node].lazy * (right - middle);
    tree[2 * node + 1].lazy += tree[node].lazy;
    tree[node].lazy = 0;
  }

  void update(int node, int left, int right, int qleft, int qright, int qval) {
    if(qleft <= left && right <= qright) {
      tree[node].sum += 1LL * qval * (right - left + 1);
      tree[node].lazy += qval;
    } else {
      propagate(node, left, right);
      int middle = (left + right) / 2;
      if(qleft <= middle) {
        update(2 * node, left, middle, qleft, qright, qval);
      }
      if(middle < qright) {
        update(2 * node + 1, middle + 1, right, qleft, qright, qval);
      }
      tree[node].sum = tree[2 * node].sum + tree[2 * node + 1].sum;
    }
  }

  void update(int left, int right, int val) {
    update(1, 0, n, left, right, val);
  }

  long long query(int node, int left, int right, int qleft, int qright) {
    if(qleft <= left && right <= qright) {
      return tree[node].sum;
    }

    propagate(node, left, right);
    int middle = (left + right) / 2;
    long long answer = 0;

    if(qleft <= middle) {
      answer += query(2 * node, left, middle, qleft, qright);
    }
    if(middle < qright) {
      answer += query(2 * node + 1, middle + 1, right, qleft, qright);
    }

    return answer;
  }

  long long query(int left, int right) {
    return query(1, 0, n, left, right);
  }
} aint;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, k;
  cin >> n >> k;
  aint.init(n + 1);
  for(int i = 1; i <= n; i++) {
    cin >> v[i];
    aint.update(i, n, v[i]);
  }

  int q;
  cin >> q;
  while(q--) {
    int type;
    cin >> type;
    if(type == 1) {
      for(int i = 1; i <= k; i++) {
        cin >> poz[i];
      }
      for(int i = 1; i < k; i++) {
        aint.update(poz[i], n, v[poz[i + 1]] - v[poz[i]]);
        new_values[i] = v[poz[i + 1]];
      }
      aint.update(poz[k], n, v[poz[1]] - v[poz[k]]);
      new_values[k] = v[poz[1]];
      for(int i = 1; i <= k; i++) {
        v[poz[i]] = new_values[i];
      }
    } else {
      int st, dr, len;
      cin >> st >> dr >> len;
      cout << aint.query(st + len - 1, dr) - aint.query(st - 1, dr - len) << "\n";
    }
  }

  return 0;
}

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