Submission #503201

#TimeUsernameProblemLanguageResultExecution timeMemory
503201desmond_willowSterilizing Spray (JOI15_sterilizing)C++17
0 / 100
147 ms5304 KiB
#include<bits/stdc++.h> using namespace std; const int MAX_N = 8 * (100069); int n, q, k; int maxtree[MAX_N]; long long int sumtree[MAX_N]; int arr[MAX_N]; void build (int l, int r, int pos) { if (l == r) { maxtree[pos] = sumtree[pos] = arr[l]; return; } int mid = (l + r)/2; build (l, mid, pos * 2); build (mid + 1, r, pos * 2 + 1); maxtree[pos] = max (maxtree[pos * 2], maxtree[pos * 2 + 1]); sumtree[pos] = sumtree[pos * 2] + sumtree[pos * 2 + 1]; } int query (int l, int r, int target_l, int target_r, int pos) { // no intersection if (r < target_l || l > target_r) {return 0;} if (target_l <= l && r <= target_r) { //total intersection #ifdef DEBUG printf ("Total intersection querying range (%d, %d): %lld\n", l, r, sumtree[pos]); #endif return sumtree[pos]; } else { //partial intersection int mid = (l + r)/2; return query(l, mid, target_l, target_r, pos*2) + query(mid + 1, r, target_l, target_r, pos*2 + 1); } } void spray (int l, int r, int target_l, int target_r, int pos) { // no intersection if (r < target_l || l > target_r || maxtree[pos] == 0) {return;} if (l == r) { maxtree[pos] = maxtree[pos] / k; sumtree[pos] = sumtree[pos] / k; return; } int mid = (l + r)/2; spray (l, mid, target_l, target_r, pos * 2); spray (mid + 1, r, target_l, target_r, pos * 2 + 1); #ifdef DEBUG printf ("Updating range sum (%d, %d) to %lld (from %lld)\n", l, r, sumtree[pos * 2] + sumtree[pos * 2 + 1], sumtree[pos]); printf ("Updating range max (%d, %d) to %d (from %d)\n", l, r, max(maxtree[pos * 2], maxtree[pos * 2 + 1]), maxtree[pos]); #endif sumtree[pos] = sumtree[pos * 2] + sumtree[pos * 2 + 1]; maxtree[pos] = max(maxtree[pos * 2], maxtree[pos * 2 + 1]); } void update (int l, int r, int pos, int index, int value) { if (l == r) { #ifdef DEBUG printf ("Updated sumtree/maxtree at %d to %d\n", index, value); #endif sumtree[pos] = value; maxtree[pos] = value; return; } int mid = (l + r)/2; if (index <= mid) { update (l, mid, pos * 2, index, value); } else { update (mid + 1, r, pos * 2 + 1, index, value); } sumtree[pos] = sumtree[pos * 2] + sumtree[pos * 2 + 1]; maxtree[pos] = max(maxtree[pos * 2], maxtree[pos * 2 + 1]); } #ifdef DEBUG void view_sumtree (int l, int r, int pos) { if (l == r) { printf ("%02lld ", sumtree[pos]); return; } int mid = (l + r)/2; view_sumtree (l, mid, pos * 2); view_sumtree (mid + 1, r, pos * 2 + 1); } void view_maxtree (int l, int r, int pos) { if (l == r) { printf ("%02d ", maxtree[pos]); return; } int mid = (l + r)/2; view_maxtree (l, mid, pos * 2); view_maxtree (mid + 1, r, pos * 2 + 1); } #endif // we can't use a range-update range-query segtree as is because // integer division is not distributive // i.e. 2//3 + 1//3 != 3//3 // thus we can't apply division to sum of dishes directly // we'll have to update all dishes individually int main () { cin >> n >> q >> k; for (int i = 1; i <= n; i++) { cin >> arr[i]; } build (1, n, 1); for (int i = 0; i < q; i++) { int op_type; cin >> op_type; if (op_type == 1) { int ind, val; cin >> ind >> val; #ifdef DEBUG printf ("Setting %d dish to %d\n", ind, val); #endif update (1, n, 1, ind, val); } else if (op_type == 2 && k > 1) { int l, r; cin >> l >> r; #ifdef DEBUG printf ("Spraying %d to %d dishes\n", l, r); #endif spray (1, n, l, r, 1); } else if (op_type == 3) { int l, r; cin >> l >> r; #ifdef DEBUG printf ("Querying amount in %d to %d dishes\n", l, r); #endif cout << query(1, n, l, r, 1) << endl; } #ifdef DEBUG view_sumtree (1, n, 1); view_maxtree (1, n, 1); cout << endl; #endif } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...