Submission #505181

#TimeUsernameProblemLanguageResultExecution timeMemory
5051810e4ef622Distributing Candies (IOI21_candies)C++17
100 / 100
660 ms55448 KiB
#include <bits/stdc++.h> #define F first #define S second #define rep(i, a, b) for(int i = (a); i < (b); ++i) #define per(i, a, b) for(int i = (b)-1; i >= (a); --i) #define bck(i, a, b) if ((i) >= (a) && (i) < (b)) #define trav(x, a) for (auto &x : (a)) #define sz(a) (int)(a).size() #define all(x) (x).begin(), (x).end() #define mp make_pair #define pb push_back #define eb emplace_back #define dbg(X) std::cerr << "[DBG]("<<__FUNCTION__<<":"<<__LINE__<<") " << #X << ": " << X << std::endl; using namespace std; typedef long long ll; typedef string str; template<typename T> using vec = vector<T>; template<typename T> using pq = priority_queue<T, vector<T>, std::greater<T>>; template<typename T> using mxpq = priority_queue<T>; typedef pair<int,int> pii; typedef vec<int> vi; typedef vec<pii> vii; typedef vec<vi> vvi; typedef pair<ll,ll> pll; typedef vec<ll> vl; typedef vec<pll> vll; typedef vec<vl> vvl; template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } template<typename A, typename B> istream& operator>>(istream& s, pair<A,B>& p) { return s>>p.first>>p.second; } template<typename A, typename B> ostream& operator<<(ostream& s, const pair<A,B>& p) { s << "(" << p.F << ", " << p.S << ")"; return s; } template<typename T> istream& operator>>(istream& s, vec<T>& p) { for (T& t : p) s >> t; return s; } template<typename T> ostream& operator<<(ostream& s, const vec<T>& p) { for (const T& t : p) s << t << " "; return s; } // monoid struct S { // id ll mn = LLONG_MAX, mx = LLONG_MIN; int mni, mxi; int i = INT_MAX; int len = 0; S() {} S(ll v, int j) : mn(v), mx(v), mni(j), mxi(j), i(j), len(1) {} S(ll mn, ll mx, int mni, int mxi, int j, int len) : mn(mn), mx(mx), mni(mni), mxi(mxi), i(j), len(len) {} S operator+(S o) { if (mn < o.mn) o.mn = mn, o.mni = mni; else if (mn == o.mn) ckmin(o.mni, mni); if (mx > o.mx) o.mx = mx, o.mxi = mxi; else if (mx == o.mx) ckmin(o.mxi, mxi); ckmin(o.i, i); o.len += len; return o; } }; // update struct U { ll v = 0; static U add(ll x) { return {x}; } // apply S operator()(S a) { a.mn += v; a.mx += v; return a; } // compose U operator()(U o) { return o.v += v, o; } }; struct seg { int l, r; S v; U u; seg *lt=0, *rt=0; seg(const vl& a) : seg(a, 0, sz(a)) {} seg(const vl& a, int l, int r) : l(l), r(r) { if (l+1 == r) v = S(a[l], l); else { int m = (l+r)/2; lt = new seg(a, l, m); rt = new seg(a, m, r); v = lt->v + rt->v; } } void update(int s, int e, U upd) { if (l >= e || r <= s) return; if (l >= s && r <= e) u = upd(u); else { push(); lt->update(s, e, upd); rt->update(s, e, upd); pull(); } } S query(int s, int e) { if (e <= l || s >= r) return S(); if (l >= s && r <= e) return u(v); else return u(lt->query(s,e) + rt->query(s,e)); } S bs(int cap, S s=S()) { auto e = u(v) + s; if (e.mx - e.mn <= cap) return e; else if (l+1 == r) return s; else { push(); pull(); e = rt->u(rt->v) + s; if (e.mx - e.mn <= cap) return lt->bs(cap, e); else return rt->bs(cap, s); } } void pull() { v = lt->u(lt->v) + rt->u(rt->v); } void push() { lt->u = u(lt->u); rt->u = u(rt->u); u = U(); } }; vi distribute_candies(vi i1, vi i2, vi i3, vi i4) { int n = sz(i1); int q = sz(i2); vl c(all(i1)); vec<pair<pii, ll>> u(sz(i2)); rep(i, 0, sz(i2)) u[i] = {{i2[i], i3[i]}, i4[i]}; trav(v, u) v.F.S++; vii ev; rep(i,0,n) ev.pb({i, INT_MAX}); rep(i,0,q) ev.pb({u[i].F.F, i}), ev.pb({u[i].F.S, -i-1}); sort(all(ev)); seg s((vl(q+1))); vi ans(n); trav(e, ev) { auto [ai, qi] = e; if (qi == INT_MAX) { S rr = s.bs(c[ai]); int r = rr.i; S w = s.query(r, q+1); ll x = s.query(q, q+1).mn; ans[ai] = x - w.mn; if (r) { ll g = s.query(r-1, r).mn; if (g < w.mn) { ans[ai] = x - w.mx + c[ai]; } } } else if (qi >= 0) { s.update(qi+1, q+1, U::add(u[qi].S)); } else { qi = -qi-1; s.update(qi+1, q+1, U::add(-u[qi].S)); } } return ans; }
#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...