Submission #471319

#TimeUsernameProblemLanguageResultExecution timeMemory
471319SoapenDeda (COCI17_deda)C++17
140 / 140
137 ms3404 KiB
// freopen("../../p257.t13.in", "r", stdin); #include <bits/stdc++.h> #define rep(a, b) for(int a = 0; a < (b); ++a) #define all(a) (a).begin(),(a).end() #define endl '\n' using namespace std; using Graph = vector<vector<int>>; using ll = long long; namespace cpc { int floor_log2(int n) { return n ? 31 - __builtin_clz(n) : 0; } int ceil_log2(int n) { return floor_log2(n) + (__builtin_popcount(n)!=1); } template<class Conf> struct SegTreeImpl { using T = typename Conf::T; // data type using U = typename Conf::U; // update type int width(int v) { return (int)n >> floor_log2(v); } int left(int v) { return width(v) * (v ^ (1 << floor_log2(v))); } int right(int v) { return left(v) + width(v); } int n; vector<T> d; // node values vector<U> lazy; // exclusive lazy SegTreeImpl(int _n) : n(1 << ceil_log2(_n)), d(2*n, Conf::NEUTRAL) { if constexpr(Conf::LAZY) lazy.resize(2*n, Conf::UNCHANGED); } void update(int i, T val) { flush(n+i); d[n+i]= val; rebuild(n+i); } void update(int l, int r, const U& upd) { flush(n + l); flush(n + r - 1); for (int li=n+l, ri =n+r; li<ri; li/=2, ri/=2) { if (li % 2) Conf::apply(*this, li++, upd); if (ri % 2) Conf::apply(*this, --ri, upd); } rebuild(trunc(n+l)); // rebuild above first changed nodes rebuild(trunc(n+r)-1); } T& query(int i) { flush(n + i); return d[n+i]; } T query(int l, int r) { flush(n + l); flush(n + r - 1); T rl = Conf::NEUTRAL, rr = Conf::NEUTRAL; for(l+=n, r+=n; l<r; l/=2, r/=2) { if(l&1) rl = Conf::combine(rl, d[l++]); if(r&1) rr = Conf::combine(d[--r], rr); } return Conf::combine(rl, rr); } // optimized iterative version for prefix search template <class Pred> int lower_bound(Pred pred) { if (!pred(d[1])) return -1; T acc = Conf::NEUTRAL; int v = 1; while(v<n) { push(v); if(!pred(Conf::combine(acc,d[v*=2]))) acc = Conf::combine(acc,d[v++]); } return v-n; } // recursive version for bin_search in range template <class Pred> T lower_bound(int l, int r, Pred pred) { T acc = Conf::NEUTRAL; return lower_bound(1,0,n,l,r,acc,pred); } private: template <class Pred> int lower_bound(int v, int l, int r, int ql, int qr, T& acc, Pred& pred) { if (r <= ql || qr<=l) return -1; if (l >= ql && r <= qr && !pred(Conf::combine(acc,d[v]))) { acc = Conf::combine(acc,d[v]); return -1; } if (l + 1 == r) return l; push(v); int m = (l+r) / 2; int res = lower_bound(v*2, l, m, ql, qr, acc, pred); if (res!=-1) return res; return lower_bound(v*2+1, m, r, ql, qr, acc, pred); } // push lazy down one layer void push(int v) { if constexpr(Conf::LAZY) { if(lazy[v]==Conf::UNCHANGED) return; Conf::apply(*this, 2*v, lazy[v]); Conf::apply(*this, 2*v+1, lazy[v]); lazy[v] = Conf::UNCHANGED; } } // push lazy updates of all parents down to v void flush(int v) { if constexpr(Conf::LAZY) { for(int b = floor_log2(v); b; --b) push(v>>b); }; } // rebuild v and all its parents void rebuild(int v) { while(v/=2) d[v] = Conf::combine(d[2*v], d[2*v+1]); } // shifts all trailing zeros away; (= first parent of v that is touched in query) int trunc(int v) { return v >> __builtin_ctz(v); } }; } const int INF = 1e9+7; struct SegTreeConf { using T = int; static constexpr T NEUTRAL = INF; static T combine(const T& a, const T& b) { return min(a,b); } // lazy part const static bool LAZY = false; using U = int; static constexpr U UNCHANGED = 0; void static apply(cpc::SegTreeImpl<SegTreeConf>& seg, int v, const U& upd) { seg.d[v] += seg.width(v)*upd; seg.lazy[v] += upd; } }; using SegTree = cpc::SegTreeImpl<SegTreeConf>; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.precision(10); int n,q; cin>>n>>q; SegTree seg(n); rep(qq,q) { char t; cin>>t; if(t=='M') { int x,i; cin>>x>>i; seg.update(i-1,x); } else { int max_stops,min_age; cin>>max_stops>>min_age; min_age--; int res = seg.lower_bound(min_age, n, [&](int acc) { return acc <= max_stops; }); cout << (res==-1 ? -1 : res+1) << endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...