Submission #1080975

#TimeUsernameProblemLanguageResultExecution timeMemory
1080975daoquanglinh2007Food Court (JOI21_foodcourt)C++17
100 / 100
575 ms56404 KiB
#include <bits/stdc++.h> using namespace std; template<bool HAS_QUERY, bool HAS_UPDATE, class T, class U, class F1, class F2, class F3> struct segment_tree_base{ static_assert(HAS_QUERY || HAS_UPDATE); #define ifQ if constexpr(HAS_QUERY) #define ifU if constexpr(HAS_UPDATE) int n, size, log; vector<T> data; vector<U> data_action; F1 TT; // monoid operation (always adjacent) T T_id; // monoid identity F2 UU; // monoid operation (superset, subset) U U_id; // monoid identity F3 UT; // action of U on T (superset, subset) // O(n) segment_tree_base(F1 TT, T T_id, F2 UU, U U_id, F3 UT): TT(TT), T_id(T_id), UU(UU), U_id(U_id), UT(UT){ } segment_tree_base &operator=(const segment_tree_base &seg){ n = seg.n; size = seg.size; log = seg.log; data = seg.data; data_action = seg.data_action; } // O(1) friend void swap(segment_tree_base &x, segment_tree_base &y){ swap(x.n, y.n); swap(x.size, y.size); swap(x.log, y.log); swap(x.data, y.data); swap(x.data_action, y.data_action); } // O(n) void build(int n){ assert(n >= 0); this->n = n; size = 1; while(size < n) size <<= 1; log = __lg(size); ifQ data.assign(size << 1, T_id); ifU data_action.assign(HAS_QUERY ? size : size << 1, U_id); } // O(n) void build(int n, T x){ static_assert(HAS_QUERY); assert(n >= 0); this->n = n; size = 1; while(size < n) size <<= 1; log = __lg(size); data.assign(size << 1, T_id); fill(data.begin() + size, data.begin() + size + n, x); for(auto i = size - 1; i >= 1; -- i) refresh(i); ifU data_action.assign(size, U_id); } // O(n) template<class V> void build(const vector<V> &a){ static_assert(HAS_QUERY); n = (int)a.size(); size = 1; while(size < n) size <<= 1; log = __lg(size); data.assign(size << 1, T_id); copy(a.begin(), a.end(), data.begin() + size); for(auto i = size - 1; i >= 1; -- i) refresh(i); ifU data_action.assign(size, U_id); } // O(n) void build_action(int n){ static_assert(!HAS_QUERY && HAS_UPDATE); assert(n >= 0); build(n); } // O(n) void build_action(int n, U f){ static_assert(!HAS_QUERY && HAS_UPDATE); assert(n >= 0); this->n = n; size = 1; while(size < n) size <<= 1; log = __lg(size); data_action.assign(size << 1, U_id); fill(data_action.begin() + size, data_action.begin() + size + n, f); } // O(n) template<class V> void build_action(const vector<V> &a){ static_assert(!HAS_QUERY && HAS_UPDATE); n = (int)a.size(); size = 1; while(size < n) size <<= 1; log = __lg(size); data_action.assign(size << 1, U_id); copy(a.begin(), a.end(), data_action.begin() + size); } // O(1) void refresh(int u){ static_assert(HAS_QUERY); data[u] = TT(data[u << 1], data[u << 1 | 1]); } // O(1) void apply(int u, U f){ static_assert(HAS_UPDATE); ifQ data[u] = UT(f, data[u]); if(!HAS_QUERY || u < size) data_action[u] = UU(f, data_action[u]); } // O(1) void push(int u){ static_assert(HAS_UPDATE); apply(u << 1, data_action[u]), apply(u << 1 | 1, data_action[u]); data_action[u] = U_id; } // O(log(n)) if HAS_UPDATE, O(1) otherwise. T query(int p){ static_assert(HAS_QUERY); assert(0 <= p && p < n); p += size; ifU for(auto i = log; i >= 1; -- i) push(p >> i); return data[p]; } // O(log(n)) U query_action(int p){ static_assert(!HAS_QUERY && HAS_UPDATE); assert(0 <= p && p < n); p += size; ifU for(auto i = log; i >= 1; -- i) push(p >> i); return data_action[p]; } // O(log(n)) T query(int ql, int qr){ static_assert(HAS_QUERY); assert(0 <= ql && ql <= qr && qr <= n); if(ql == qr) return T_id; ql += size, qr += size; ifU for(auto i = log; i >= 1; -- i){ if(ql >> i << i != ql) push(ql >> i); if(qr >> i << i != qr) push(qr >> i); } T res_left = T_id, res_right = T_id; for(; ql < qr; ql >>= 1, qr >>= 1){ if(ql & 1) res_left = TT(res_left, data[ql ++]); if(qr & 1) res_right = TT(data[-- qr], res_right); } return TT(res_left, res_right); } // O(1) T query_all() const{ static_assert(HAS_QUERY); return data[1]; } // O(n) vector<T> to_array(){ static_assert(HAS_QUERY); ifU for(auto u = 1; u < size; ++ u) push(u); return vector<T>(data.begin() + size, data.begin() + size + n); } // O(n) vector<U> to_array_of_updates(){ static_assert(!HAS_QUERY && HAS_UPDATE); for(auto u = 1; u < size; ++ u) push(u); return vector<U>(data_action.begin() + size, data_action.begin() + size + n); } // O(log(n)) void set(int p, T x){ static_assert(HAS_QUERY); assert(0 <= p && p < n); p += size; ifU for(auto i = log; i >= 1; -- i) push(p >> i); data[p] = x; for(auto i = 1; i <= log; ++ i) refresh(p >> i); } // O(log(n)) void set_action(int p, U f){ static_assert(!HAS_QUERY && HAS_UPDATE); assert(0 <= p && p < n); p += size; for(auto i = log; i >= 1; -- i) push(p >> i); data_action[p] = f; } // O(log(n)) void update(int p, U f){ static_assert(HAS_UPDATE); assert(0 <= p && p < n); p += size; for(auto i = log; i >= 1; -- i) push(p >> i); ifQ{ data[p] = UT(f, data[p]); for(auto i = 1; i <= log; ++ i) refresh(p >> i); } else data_action[p] = UU(f, data_action[p]); } // O(log(n)) void update(int ql, int qr, U f){ static_assert(HAS_UPDATE); assert(0 <= ql && ql <= qr && qr <= n); if(ql == qr) return; ql += size, qr += size; for(auto i = log; i >= 1; -- i){ if(ql >> i << i != ql) push(ql >> i); if(qr >> i << i != qr) push(qr >> i); } int _ql = ql, _qr = qr; for(; ql < qr; ql >>= 1, qr >>= 1){ if(ql & 1) apply(ql ++, f); if(qr & 1) apply(-- qr, f); } ql = _ql, qr = _qr; ifQ for(auto i = 1; i <= log; ++ i){ if(ql >> i << i != ql) refresh(ql >> i); if(qr >> i << i != qr) refresh(qr >> i); } } void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){ static_assert(HAS_QUERY && HAS_UPDATE); assert(0 <= ql && ql <= qr && qr <= n); if(ql == qr) return; ql += size, qr += size; for(auto i = log; i >= 1; -- i){ if(ql >> i << i != ql) push(ql >> i); if(qr >> i << i != qr) push(qr >> i); } auto recurse = [&](auto self, int u)->void{ if(exit_rule(data[u])) return; if(enter_rule(data[u])){ apply(u, update_rule(data[u])); return; } push(u); self(self, u << 1), self(self, u << 1 | 1); refresh(u); }; int _ql = ql, _qr = qr; for(; ql < qr; ql >>= 1, qr >>= 1){ if(ql & 1) recurse(recurse, ql ++); if(qr & 1) recurse(recurse, -- qr); } ql = _ql, qr = _qr; for(auto i = 1; i <= log; ++ i){ if(ql >> i << i != ql) refresh(ql >> i); if(qr >> i << i != qr) refresh(qr >> i); } } // pred(sum[ql, r)) is T, T, ..., T, F, F, ..., F // Returns max r with T // O(log(n)) int max_pref(int ql, auto pred){ static_assert(HAS_QUERY); assert(0 <= ql && ql <= n && pred(T_id)); if(ql == n) return n; ql += size; ifU for(auto i = log; i >= 1; -- i) push(ql >> i); T sum = T_id; do{ while(~ql & 1) ql >>= 1; if(!pred(TT(sum, data[ql]))){ while(ql < size){ ifU push(ql); ql = ql << 1; if(pred(TT(sum, data[ql]))) sum = TT(sum, data[ql ++]); } return ql - size; } sum = TT(sum, data[ql]); ++ ql; }while((ql & -ql) != ql); return n; } // pred(sum[l, qr)) is F, F, ..., F, T, T, ..., T // Returns min l with T // O(log(n)) int max_suff(int qr, auto pred){ static_assert(HAS_QUERY); assert(0 <= qr && qr <= n && pred(T_id)); if(qr == 0) return 0; qr += size; ifU for(auto i = log; i >= 1; -- i) push(qr - 1 >> i); T sum = T_id; do{ -- qr; while(qr > 1 && qr & 1) qr >>= 1; if(!pred(TT(data[qr], sum))){ while(qr < size){ ifU push(qr); qr = qr << 1 | 1; if(pred(TT(data[qr], sum))) sum = TT(data[qr --], sum); } return qr + 1 - size; } sum = TT(data[qr], sum); }while((qr & -qr) != qr); return 0; } template<class output_stream> friend output_stream &operator<<(output_stream &out, segment_tree_base<HAS_QUERY, HAS_UPDATE, T, U, F1, F2, F3> seg){ out << "{"; for(auto i = 0; i < seg.n; ++ i){ ifQ out << seg.query(i); else out << seg.query_action(i); if(i != seg.n - 1) out << ", "; } return out << '}'; } #undef ifQ #undef ifU }; // Supports query template<class T, class F> auto make_Q_segment_tree(F TT, T T_id){ using U = int; auto _UU = [&](U, U)->U{ return U{}; }; auto _UT = [&](U, T)->T{ return T{}; }; return segment_tree_base<true, false, T, U, F, decltype(_UU), decltype(_UT)>(TT, T_id, _UU, U{}, _UT); } // Supports update template<class U, class F> auto make_U_segment_tree(F UU, U U_id){ using T = int; auto _TT = [&](T, T)->T{ return T{}; }; auto _UT = [&](U, T)->T{ return T{}; }; return segment_tree_base<false, true, T, U, decltype(_TT), F, decltype(_UT)>(_TT, T{}, UU, U_id, _UT); } // Supports query and update template<class T, class U, class F1, class F2, class F3> auto make_QU_segment_tree(F1 TT, T T_id, F2 UU, U U_id, F3 UT){ return segment_tree_base<true, true, T, U, F1, F2, F3>(TT, T_id, UU, U_id, UT); } #define ll long long #define pii pair <int, int> #define pli pair <ll, int> #define fi first #define se second #define mp make_pair const int NM = 2.5e5; const ll inf = 1e18; using T1 = pli; struct __TT1{ T1 operator()(const T1& lhs, const T1& rhs){ if (lhs.fi < rhs.fi) return lhs; return rhs; } } TT1; T1 T1_id = mp(+inf, 0); using T2 = ll; struct __TT2{ T2 operator()(const T2& lhs, const T2& rhs){ return max(lhs, rhs); } } TT2; T2 T2_id = 0; using U = ll; struct __UU{ U operator()(const U& up, const U& down){ return up+down; } } UU; U U_id = 0; struct __UT1{ T1 operator()(const U& up, const T1& down){ T1 res; res.fi = down.fi+up; res.se = down.se; return res; } } UT1; struct __UT2{ T2 operator()(const U& up, const T2& down){ return up+down; } } UT2; int N, M, Q; vector <T1> arr; vector <pair <int, pii> > upd[NM+5]; vector <pli> qry[NM+5]; bool has_query[NM+5]; int grp[NM+5], ans[NM+5]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M >> Q; segment_tree_base st1 = make_QU_segment_tree(TT1, T1_id, UU, U_id, UT1); segment_tree_base st2 = make_QU_segment_tree(TT2, T2_id, UU, U_id, UT2); segment_tree_base st3 = make_QU_segment_tree(TT2, T2_id, UU, U_id, UT2); arr.resize(Q+1); for (int i = 0; i <= Q; i++) arr[i] = mp(0, i); st1.build(arr); st2.build(Q+1, 0); st3.build(Q+1, 0); for (int i = 1; i <= Q; i++){ int type; cin >> type; if (type == 1){ int l, r, c, k; cin >> l >> r >> c >> k; grp[i] = c; upd[l].push_back(mp(i, mp(1, k))); upd[r+1].push_back(mp(i, mp(1, -k))); } else if (type == 2){ int l, r, k; cin >> l >> r >> k; upd[l].push_back(mp(i, mp(2, k))); upd[r+1].push_back(mp(i, mp(2, -k))); } else{ int a; ll b; cin >> a >> b; qry[a].push_back(mp(b, i)); has_query[i] = 1; } } for (int i = 1; i <= N; i++){ for (pair <int, pii> p : upd[i]){ st1.update(p.fi, Q+1, (p.se.fi == 1 ? p.se.se : -p.se.se)); if (p.se.fi == 1) st2.update(p.fi, Q+1, p.se.se); else st3.update(p.fi, Q+1, p.se.se); } for (pli p : qry[i]){ int r = p.se, l = st1.query(0, r+1).se; if (st1.query(r).fi-st1.query(l).fi < p.fi){ ans[r] = 0; continue; } p.fi += st3.query(r)+st1.query(l).fi; ans[r] = grp[st2.max_pref(l+1, [&](const T2& node){return node < p.fi;})]; } } for (int i = 1; i <= Q; i++) if (has_query[i]) cout << ans[i] << '\n'; return 0; }

Compilation message (stderr)

foodcourt.cpp:215:36: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  215 |  void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                    ^~~~
foodcourt.cpp:215:52: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  215 |  void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                                    ^~~~
foodcourt.cpp:215:69: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  215 |  void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                                                     ^~~~
foodcourt.cpp:248:23: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  248 |  int max_pref(int ql, auto pred){
      |                       ^~~~
foodcourt.cpp:273:23: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  273 |  int max_suff(int qr, auto pred){
      |                       ^~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...