Submission #582522

#TimeUsernameProblemLanguageResultExecution timeMemory
582522talant117408Addk (eJOI21_addk)C++17
100 / 100
533 ms21220 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define long unsigned long #define pb push_back #define mp make_pair #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define lb lower_bound #define ub upper_bound #define sz(v) int((v).size()) #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl '\n' #define PI 2*acos(0.0) const int N = 1e5+7; ll tree[3][N*4]; // 0 - sum = A1 + A2 ... + An, 1 - pref = 1*A1 + 2*A2 ... + n*An, 2 - suff = n*A1 + (n-1)*A2 ... + 1*an void update(int i, int v, int l, int r, int pos, ll val) { if (l == r) { tree[i][v] = val; return; } int mid = (l+r) >> 1; if (pos <= mid) update(i, v*2, l, mid, pos, val); else update(i, v*2+1, mid+1, r, pos, val); tree[i][v] = tree[i][v*2] + tree[i][v*2+1]; } ll get(int i, int v, int l, int r, int ql, int qr) { if (ql > r || l > qr) return 0; if (ql <= l && r <= qr) return tree[i][v]; int mid = (l+r) >> 1; return get(i, v*2, l, mid, ql, qr) + get(i, v*2+1, mid+1, r, ql, qr); } struct query { int type; vector <int> inds; query() {} }; void solve() { int n, k; cin >> n >> k; vector <ll> v(n+1); for (int i = 1; i <= n; i++) { cin >> v[i]; } int q; cin >> q; vector <query> queries(q); for (int i = 0; i < q; i++) { int type; cin >> type; queries[i].type = type; if (type == 1) { for (int j = 0; j < k; j++) { int x; cin >> x; queries[i].inds.pb(x); } } else { int l, r, m; cin >> l >> r >> m; queries[i].inds.pb(l); queries[i].inds.pb(r); queries[i].inds.pb(m); } } for (int i = 1; i <= n; i++) { update(0, 1, 1, n, i, v[i]); update(1, 1, 1, n, i, v[i] * i); update(2, 1, 1, n, i, v[i] * (n-i+1)); } for (auto to : queries) { auto type = to.type; auto ind = to.inds; if (type == 1) { vector <int> new_order; for (int j = 1; j < k; j++) new_order.pb(v[ind[j]]); new_order.pb(v[ind[0]]); for (int j = 0; j < k; j++) { v[ind[j]] = new_order[j]; update(0, 1, 1, n, ind[j], v[ind[j]]); update(1, 1, 1, n, ind[j], v[ind[j]] * ind[j]); update(2, 1, 1, n, ind[j], v[ind[j]] * (n-ind[j]+1)); } } else { ll l = ind[0], r = ind[1], m = ind[2]; m = min(m, r-l+1-m+1); ll ans = 0; ans += get(1, 1, 1, n, l, l+m-2) - get(0, 1, 1, n, l, l+m-2) * (l-1); ans += get(0, 1, 1, n, l+m-1, r-m+1) * m; ans += get(2, 1, 1, n, r-m+2, r) - get(0, 1, 1, n, r-m+2, r) * (n-r); cout << ans << endl; } } } int main() { do_not_disturb int t = 1; //~ cin >> t; while (t--) { solve(); } return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...