Submission #1010234

#TimeUsernameProblemLanguageResultExecution timeMemory
1010234LilPlutonAddk (eJOI21_addk)C++14
0 / 100
157 ms4952 KiB
#include <bits/stdc++.h> /// author: LilPluton auuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu using namespace std; #define ll long long const int N = 1e5 + 5; int n, k, q, l, r, m, ty; int a[N], lz[N * 4], t[4 * N]; void relax(int id, int l, int r){ if (!lz[id]) return; int m = (l + r) >> 1; t[id << 1] += (m - l + 1) * lz[id]; t[id << 1 | 1] += (r - m) * lz[id]; lz[id << 1] += lz[id]; lz[id << 1 | 1] += lz[id]; lz[id] = 0; } void update(int id, int l, int r, int u, int v, int val){ if (u > r || v < l) return; if (u <= l && v >= r){ t[id] += (r - l + 1) * val; lz[id] += val; return; } int m = (l + r) >> 1; relax(id, l, r); update(id << 1, l, m, u, v, val); update(id << 1 | 1, m + 1, r, u, v, val); t[id] = t[id << 1] + t[id << 1 | 1]; } int getans(int id, int l, int r, int u, int v){ if (u > r || v < l) return 0; if (u <= l && v >= r) return t[id]; int m = (l + r) >> 1; relax(id, l, r); int ql = getans(id << 1, l, m, u, v); int qr = getans(id << 1 | 1, m + 1, r, u, v); return (ql + qr); } signed main() { cin >> n >> k; for(int i = 1; i <= n; ++i) cin >> a[i], update(1,1,n,i,n,a[i]); cin >> q; while(q--) { cin >> ty; if(ty == 1) { vector<int>pos(k), val; for(int &v : pos) cin >> v; for(int j = 1; j < k; ++j) val.push_back(a[pos[j]]); val.push_back(a[pos[0]]); for(int j = 0; j < k; ++j) { update(1,1,n,pos[j], n, val[j] - a[pos[j]]); a[pos[j]] = val[j]; } } else { cin >> l >> r >> m; cout << getans(1,1,n,l + m - 1, r) - getans(1,1, n, l - 1, r - m) << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...