Submission #1298241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298241		reginox	Addk (eJOI21_addk)	C++20	100 / 100	205 ms	6408 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int N = 1e5+3;
int n, k, a[N];
ll seg[N<<2], add[N<<2];

void down(int id, int l, int r){
  int mid = (l+r)/2;
  seg[id*2] += add[id] * (mid-l+1);
  seg[id*2+1] += add[id] * (r - mid);
  add[id*2] += add[id];
  add[id*2+1] += add[id];
  add[id] = 0;
  return ;
}

void upd(int id, int l, int r, int u, int v, ll w){
  if(v < l || r < u) return ;
  if(u <= l && r <= v){
    seg[id] += w * (r-l+1);
    add[id] += w;
    return ;
  }
  down(id, l, r);
  int mid = (l+r)/2;
  upd(id*2, l, mid, u, v, w);
  upd(id*2+1, mid+1, r, u, v, w);
  seg[id] = seg[id*2] + seg[id*2+1];
}

ll get(int id, int l, int r, int u, int v){
  if(v < l || r < u) return 0;
  if(u <= l && r <= v) return seg[id];
  down(id, l, r);
  int mid = (l+r)/2;
  return get(id*2, l, mid, u, v) + get(id*2+1, mid+1, r, u, v);
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> k;
  for(int i = 1; i <= n; i++) cin >> a[i];
  int q; cin >> q;
  vector<int> v(k);
  ll z = 0;
  for(int i = 1; i <= n; i++){
    z += a[i];
    upd(1, 1, n, i, i, z);
  }
  while(q--){
    int t; cin >> t;
    if(t == 1){
      for(auto &x:v) cin >> x;
      int fi = a[v[0]];
      for(int i = 0; i < k; i++){
        int &cur = a[v[i]];
        if(i == k - 1){
          upd(1, 1, n, v[i], n, fi - cur);
          cur = fi;
        }
        else{
          upd(1, 1, n, v[i], n, a[v[i+1]] - a[v[i]]);
          a[v[i]] = a[v[i+1]];
        }
      }
      // for(int i = 1; i <= n; i++) cout << a[i] << " ";
      // cout << "\n";
      // for(int i = 1; i <= n; i++) cout << get(1, 1, n, i, i) << " ";
      // cout << "\n";
    }
    else{
      int l, r, m;
      cin >> l >> r >> m;
      // cout << l+m-1 << " " << r << " " << l-1 << " " << r-m << "\n";
      // cout << get(1, 1, n, l+m-1, r) << "\n";
      // cout << get(1, 1, n, max(1, l-1), r-m) << "\n";
      cout << get(1, 1, n, l+m-1, r) - get(1, 1, n, max(1, l-1), r-m) << "\n";
    }
  }
  return 0;
}

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