Submission #1209808

#TimeUsernameProblemLanguageResultExecution timeMemory
1209808sunflowerAddk (eJOI21_addk)C++17
92 / 100
38 ms3912 KiB
#include <bits/stdc++.h> using namespace std; int n, numPerm, q; #define MAX_N 100'100 int a[MAX_N + 2]; int id[12]; long long pre[MAX_N + 2], sum[MAX_N + 2]; #undef MAX_N int main() { ios_base::sync_with_stdio(false);cin.tie(nullptr); // freopen("test.inp","r",stdin); // freopen("test.out","w",stdout); cin >> n >> numPerm; pre[0] = sum[0] = 0; for (int i = 1; i <= n; ++i) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; sum[i] = sum[i - 1] + 1LL * a[i] * i; } cin >> q; while (q--) { int type; cin >> type; if (type == 1) { for (int i = 1; i <= numPerm; ++i) cin >> id[i]; } else { int L, R, range; cin >> L >> R >> range; if (R - L + 1 < range) {cout << "0\n"; continue;} int num = (R - L + 1) - range + 1; range = min(range, num); long long ans = 0; int pref = L + range - 2; ans += sum[pref] - sum[L - 1] - 1LL * (L - 1) * (pre[pref] - pre[L - 1]); L = pref + 1; int rig = max(pref + 1, R - range + 2); if (rig <= R) { ans += 1LL * (R + 1) * (pre[R] - pre[rig - 1]) - (sum[R] - sum[rig - 1]); } R = rig - 1; if (L <= R) { ans += 1LL * range * (pre[R] - pre[L - 1]); } cout << ans << "\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...