Submission #1201502

#TimeUsernameProblemLanguageResultExecution timeMemory
1201502HappyCapybaraDistributing Candies (IOI21_candies)C++17
27 / 100
1612 ms51320 KiB
#include "candies.h" #include<bits/stdc++.h> using namespace std; int n, k; vector<vector<int>> st; vector<int> merge(vector<int> a, vector<int> b){ pair<int,int> na = {a[0]+a[2], a[1]+a[2]}; pair<int,int> ab = {max(na.first, b[0]), min(na.second, b[1])}; if (b[0] > ab.second) ab = {b[0], b[0]}; if (b[1] < ab.first) ab = {b[1], b[1]}; pair<int,int> oa = {ab.first-a[2], ab.second-a[2]}; return {oa.first, oa.second, ab.first-oa.first+b[2]}; } void pushdown(int node, int tl, int tr){ if (tl == tr) return; st[node*2] = merge(st[node*2], st[node]); st[node*2+1] = merge(st[node*2+1], st[node]); st[node] = {0, k, 0}; } void update(int l, int r, int v, int node=1, int tl=0, int tr=n-1){ pushdown(node, tl, tr); if (l <= tl && tr <= r){ if (v > 0) st[node] = merge(st[node], {0, k-min(k, v), min(k, v)}); else st[node] = merge(st[node], {min(k, -v), k, max(-k, v)}); return; } int tm = (tl+tr)/2; if (l <= tm) update(l, r, v, node*2, tl, tm); if (tm+1 <= r) update(l, r, v, node*2+1, tm+1, tr); } int query(int pos){ int node = 1, tl = 0, tr = n-1; while (tl != tr){ int tm = (tl+tr)/2; if (pos <= tm){ node = node*2; tr = tm; } else { node = node*2+1; tl = tm+1; } } vector<int> res = {0, k, 0}; while (true){ res = merge(res, st[node]); if (node == 1) break; node >>= 1; } return res[0]+res[2]; } vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){ n = c.size(); k = c[0]; st.resize(4*n, {0, k, 0}); int q = l.size(); /*vector<int> res = {0, k, 0}; for (int i=0; i<q; i++){ res = merge(res, {max(0, min(k, -v[i])), min(k, k-min(k, v[i])), v[i]}); cout << res[0] << " " << res[1] << " " << res[2] << endl; }*/ for (int i=0; i<q; i++) update(l[i], r[i], v[i]); vector<int> res(n); for (int i=0; i<n; i++) res[i] = query(i); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...