# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
471318 | Soapen | Deda (COCI17_deda) | C++17 | 135 ms | 3428 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 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);
}
template <class Pred>
int lower_bound(Pred pred) {
if (!pred(d[1])) return -1;
return lower_bound_unchecked(1,Conf::NEUTRAL,pred);
}
template <class Pred>
T lower_bound(int l, int r, Pred pred) {
T acc = Conf::NEUTRAL;
return search(1,0,n,l,r,acc,pred);
/*
flush(n + l);
flush(n + r - 1);
vector<int> segs, rsegs;
for(l+=n, r+=n; l<r; l/=2, r/=2) {
if(l&1) segs.push_back(l++);
if(r&1) rsegs.push_back(--r);
}
segs.insert(end(segs), rbegin(rsegs), rend(rsegs));
T acc = Conf::NEUTRAL;
for(auto v : segs) {
if(pred(Conf::combine(acc,d[v])))
return lower_bound_unchecked(v,acc,pred);
acc = Conf::combine(acc,d[v]);
}
return -1;
*/
}
template <class Pred>
int search(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) {
if(pred(Conf::combine(acc,d[v])))
return lower_bound_unchecked(v,acc,pred);
acc = Conf::combine(acc,d[v]);
return -1;
}
push(v);
int m = (l+r) / 2;
int res = search(v*2, l, m, ql, qr, acc, pred);
if (res!=-1) return res;
return search(v*2+1, m, r, ql, qr, acc, pred);
}
private:
// lower bound in node (requires the solution to be in subarray of v)
template<class Pred>
int lower_bound_unchecked(int v, T acc, Pred pred) {
while(v<n) {
push(v);
if(!pred(Conf::combine(acc,d[v*=2])))
acc = Conf::combine(acc,d[v++]);
}
return v-n;
}
// 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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |