Submission #825588

#TimeUsernameProblemLanguageResultExecution timeMemory
825588kebineAddk (eJOI21_addk)C++17
92 / 100
2066 ms6496 KiB
#include<bits/stdc++.h> using namespace std; #define ioss ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define int long long #define tup tuple<int, int, int> #define pii pair<int, int> #define fi first #define se second #define pub push_back #define pob pop_back int n, k, q; vector<int> arr; vector<int> segtr; void build(int i, int l, int r) { if(l == r) { segtr[i] = arr[l]; return; } int mid = (l+r)/2; build(i*2, l, mid); build(i*2+1, mid+1, r); segtr[i] = segtr[i*2] + segtr[i*2+1]; } void update(int i, int l, int r, int idx, int val) { if(l == r) { segtr[i] = val; return; } int mid = (l+r)/2; if(idx <= mid) update(i*2, l, mid, idx, val); else update(i*2+1, mid+1, r, idx, val); segtr[i] = segtr[i*2] + segtr[i*2+1]; } int query(int i, int l, int r, int ql, int qr) { if(ql <= l && qr >= r) return segtr[i]; if(ql > r || qr < l) return 0; int mid = (l+r)/2; return query(i*2, l, mid, ql, qr) + query(i*2+1, mid+1, r, ql, qr); } signed main() { ioss; cin >> n >> k; segtr.assign(4*n, 0); arr.resize(n+2); int pref[n+2] = {}; for(int i = 1; i <= n; i++) cin >> arr[i], pref[i] = pref[i-1]+arr[i]; build(1, 1, n); if(k == 1) { cin >> q; for(int i = 0; i < q; i++) { int idx; cin >> idx; if(idx == 1) { int num; cin >> num; } else { int l, r, m; cin >> l >> r >> m; int ans = 0; if(m > (r-l+1)/2) m = (r-l+1)-m+1; for(int j = 0; j < m; j++) ans += pref[r-j]-pref[l+j-1]; cout << ans << endl; } } } else { cin >> q; for(int i = 0; i < q; i++) { int idx; cin >> idx; if(idx == 1) { int num1 = 0, num2 = 0; for(int j = 1; j <= k; j++) { if(j == 1) { cin >> num1; continue; } else cin >> num2; swap(arr[num1], arr[num2]); update(1, 1, n, num1, arr[num1]); num1 = num2; } update(1, 1, n, num2, arr[num2]); // for(int i = 1; i <= 4*n; i++) cout << " :: " << i << " " << segtr[i] << endl; } else { int l, r, m; cin >> l >> r >> m; int ans = 0; if(m > (r-l+1)/2) m = (r-l+1)-m+1; for(int j = 0; j < m; j++) ans += query(1, 1, n, l+j, r-j); cout << ans << endl; } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...