Submission #989963

#TimeUsernameProblemLanguageResultExecution timeMemory
989963LOLOLOAddk (eJOI21_addk)C++17
92 / 100
109 ms15816 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (ll)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 4e5 + 1000; ll sz[N], seg[N], laz[N]; void push(int id) { ll t = laz[id]; laz[id * 2] += t; laz[id * 2 + 1] += t; seg[id * 2] += sz[id * 2] * t; seg[id * 2 + 1] += sz[id * 2 + 1] * t; laz[id] = 0; } void build(int id, int l, int r) { sz[id] = r - l + 1; if (l == r) return; int m = (l + r) / 2; build(id * 2, l, m); build(id * 2 + 1, m + 1, r); } void upd(int id, int l, int r, int u, int v, ll c) { if (l > v || r < u) return; if (l >= u && r <= v) { seg[id] += sz[id] * c; laz[id] += c; return; } push(id); int m = (l + r) / 2; upd(id * 2, l, m, u, v, c); upd(id * 2 + 1, m + 1, r, u, v, c); seg[id] = seg[id * 2] + seg[id * 2 + 1]; } ll range(int id, int l, int r, int u, int v) { if (l > v || r < u || u > v) return 0; if (l >= u && r <= v) { return seg[id]; } push(id); int m = (l + r) / 2; return range(id * 2, l, m, u, v) + range(id * 2 + 1, m + 1, r, u, v); } ll a[N]; void solve() { int n, k; cin >> n >> k; build(1, 0, n); for (int i = 1; i <= n; i++) { cin >> a[i]; upd(1, 0, n, i, n, a[i]); } int q; cin >> q; for (int i = 1; i <= q; i++) { int t; cin >> t; if (t == 1) { vector <int> val, pos; int fs = -1; for (int j = 0; j < k; j++) { int x; cin >> x; if (fs == -1) { fs = a[x]; } else { val.pb(a[x]); } pos.pb(x); } val.pb(fs); for (int j = 0; j < k; j++) { upd(1, 1, n, pos[j], n, val[j] - a[pos[j]]); a[pos[j]] = val[j]; } } else { int l, r, m; cin >> l >> r >> m; cout << range(1, 0, n, l + m - 1, r) - range(1, 0, n, l - 1, r - m) << '\n'; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) { solve(); } return 0; } /* 8 3 7 2 5 1 9 3 4 6 3 2 2 7 5 1 2 5 8 2 2 7 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...