Submission #1207797

#TimeUsernameProblemLanguageResultExecution timeMemory
1207797tkm_algorithmsDistributing Candies (IOI21_candies)C++20
0 / 100
444 ms22792 KiB
/** * In the name of Allah * We are nothing and you're everything **/ #include <bits/stdc++.h> #include "candies.h" using namespace std; using ll = long long; using ull = int64_t; #define all(x) begin(x), end(x) #define sz(x) (ll)(x).size() //#define ll long long const char nl = '\n'; const ll N = 2e5+1; const ll inf = 0x3f3f3f3f3f3f3f3fll; const ll mod = 1e9+7; vector<ll> p(N+1); struct node { ll set, sum, lz; node() { set = -1, sum = 0, lz = 0; } }; struct segtree { vector<node> tree; ll size; void init(ll n) { size = 1; while (size < n)size <<= 1; tree.assign(2*size-1, node()); } void apply(ll x, ll v) { tree[x].sum = tree[x].set = v; tree[x].lz = 0; } void add(ll x, ll v) { tree[x].sum += v, tree[x].lz += v; } void push(ll x, ll y, ll lx, ll rx, ll lef) { if (tree[x].set != -1) { if (tree[x].set == 0)apply(y, tree[x].set); else { int mid = lx+rx>>1; apply(y, (!lef?p[mid]-p[lx]:p[rx-mid])); } tree[x].set = -1; } if (tree[x].lz != 0) { add(y, tree[x].lz); tree[x].lz = 0; } } void radd(ll l, ll r, ll v, ll x, ll lx, ll rx) { if (rx <= l || r <= lx)return; if (lx >= l && rx <= r) { add(x, v); return; } node a = tree[x]; push(x, 2*x+1, lx, rx, 0); tree[x] = a; push(x, 2*x+2, lx, rx, 1); int mid = lx+rx>>1; radd(l, r, v, 2*x+1, lx, mid); radd(l, r, v, 2*x+2, mid, rx); tree[x].sum = tree[2*x+1].sum+tree[2*x+2].sum; } void radd(ll l, ll r, ll v) { radd(l, r, v, 0, 0, size); } void set0(ll l, ll r, ll x, ll lx, ll rx) { if (rx <= l || r <= lx)return; if (lx >= l && rx <= r) { apply(x, 0); return; } node a = tree[x]; push(x, 2*x+1, lx, rx, 0); tree[x] = a; push(x, 2*x+2, lx, rx, 1); int mid = lx+rx>>1; set0(l, r, 2*x+1, lx, mid); set0(l, r, 2*x+2, mid, rx); tree[x].sum = tree[2*x+1].sum+tree[2*x+2].sum; } void set0(ll l, ll r) { set0(l, r, 0, 0, size); } void setmx(ll l, ll r, ll x, ll lx, ll rx) { if (rx <= l || r <= lx)return; if (lx >= l && rx <= r) { tree[x].sum = tree[x].set = p[rx]-p[lx]; tree[x].lz = 0; return; } node a = tree[x]; push(x, 2*x+1, lx, rx, 0); tree[x] = a; push(x, 2*x+2, lx, rx, 1); ll mid = lx+rx>>1; setmx(l, r, 2*x+1, lx, mid); setmx(l, r, 2*x+2, mid, rx); tree[x].sum = tree[2*x+1].sum+tree[2*x+2].sum; } void setmx(ll l, ll r) { setmx(l, r, 0, 0, size); } ll get(ll i, ll x, ll lx, ll rx) { if (rx-lx==1)return tree[x].sum; ll mid = lx+rx>>1; node a = tree[x]; push(x, 2*x+1, lx, rx, 0); tree[x] = a; push(x, 2*x+2, lx, rx, 1); if (i < mid)return get(i, 2*x+1, lx, mid); else return get(i, 2*x+2, mid, rx); tree[x].sum = tree[2*x+1].sum+tree[2*x+2].sum; } ll get(ll i) { return get(i, 0, 0, size); } }; vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) { ll n = sz(c), q = sz(l); vector<pair<int, int>> b; for (int i = 0; i < n; ++i)b.push_back(make_pair(c[i], i)); sort(all(b)); sort(all(c)); for (ll i = 1; i <= n; ++i)p[i] = c[i-1]+p[i-1]; segtree st; st.init(n+1); for (ll i = 0; i < q; ++i) { st.radd(l[i], r[i]+1, v[i]); if (v[i] > 0) { ll a = st.get(i); if (a <= c[0])continue; ll lx = 0, rx = n; while (rx-lx>1) { ll mid = lx+rx>>1; if (st.get(mid) <= c[mid])rx = mid; else lx = mid; } st.setmx(0, lx+1); } if (v[i] < 0){ ll a = st.get(i); if (a >= 0)continue; ll lx = 0, rx = n; while (rx-lx>1) { ll mid = lx+rx>>1; if (st.get(mid) >= 0)rx = mid; else lx = mid; } st.set0(0, lx+1); } } vector<int> res(n); for (ll i = 0; i < n; ++i) res[b[i].second] = st.get(i); return res; } //int main() { //vector<int> ans = distribute_candies({(int)1e9, (int)1e9, 15}, {0, 0, 0}, {2, 2, 2}, {(int)1e9, (int)-1e9, (int)1e9}); //for (auto &i: ans)cout << i << " "; //return 0; //}
#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...