Submission #471319

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
471319	2021-09-08T09:39:21 Z	Soapen	Deda (COCI17_deda)	C++17	140 / 140	137 ms	3404 KB

deda

// 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;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	3 ms	332 KB	Output is correct
4	Correct	137 ms	3404 KB	Output is correct
5	Correct	112 ms	2048 KB	Output is correct
6	Correct	122 ms	3196 KB	Output is correct
7	Correct	127 ms	3236 KB	Output is correct