oj.uz

Submission #1086546

# Submission time Handle Problem Language Result Execution time Memory
1086546 2024-09-11T02:32:08 Z CDuong Passport (JOI23_passport) C++17
100 / 100
 338 ms 42876 KB 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
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 min_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);
}

const int oo = 1e9;

void solve() {
    int n;
    cin >> n;

    vector<int> L(n), R(n);
    for (int i = 0; i < n; ++i) {
        cin >> L[i] >> R[i];
        --L[i];
    }

    vector<vector<int>> rgs(2 * n);
    for (int i = 0; i < n; ++i) {
        int ql = L[i] + n, qr = R[i] + n;
        for (; ql < qr; ql >>= 1, qr >>= 1) {
            if (ql & 1) rgs[ql++].emplace_back(i);
            if (qr & 1) rgs[--qr].emplace_back(i);
        }
    }

    auto dijk = [&](const vector<int> &vec) -> vector<int> {
        vector<int> dis(2 * n, oo);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (int i = 0; i < n; ++i) if (vec[i] != oo) {
            dis[i + n] = vec[i];
            pq.emplace(dis[i + n], i + n);
        }

        auto upd = [&](int idx, int val) -> void {
            if (dis[idx] > val) {
                dis[idx] = val;
                pq.emplace(dis[idx], idx);
            }
        };

        while (not pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (dis[u] != d) continue;
            if (u) {
                upd(u >> 1, d);
            }
            for (auto idx : rgs[u]) {
                upd(idx + n, d + 1);
            }
        }
        return {dis.begin() + n, dis.end()};
    };

    vector<int> tost(n, oo);
    tost[0] = 0;
    tost = dijk(tost);
    tost[0] = 1;

    vector<int> toen(n, oo);
    toen[n - 1] = 0;
    toen = dijk(toen);
    toen[n - 1] = 1;

    vector<int> res(n, oo);
    for (int i = 0; i < n; ++i) res[i] = min(res[i], tost[i] + toen[i]);
    res = dijk(res);
    
    int q; cin >> q;
    while (q--) {
        int u; cin >> u;
        cout << (res[--u] == oo ? -1 : res[u] - 1) << "\n";
    }
}

signed main() {

#ifndef CDuongg
    if (fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

Compilation message

passport.cpp:225:39: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  225 |     void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                       ^~~~
passport.cpp:225:55: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  225 |     void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                                       ^~~~
passport.cpp:225:72: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  225 |     void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                                                        ^~~~
passport.cpp:258:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  258 |     int max_pref(int ql, auto pred){
      |                          ^~~~
passport.cpp:283:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  283 |     int min_suff(int qr, auto pred){
      |                          ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 294 ms 40992 KB Output is correct
5 Correct 166 ms 31532 KB Output is correct
6 Correct 95 ms 30804 KB Output is correct
7 Correct 140 ms 31680 KB Output is correct
8 Correct 64 ms 27424 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 4 ms 860 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 3 ms 860 KB Output is correct
20 Correct 2 ms 600 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 2 ms 756 KB Output is correct
24 Correct 1 ms 600 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 4 ms 860 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 3 ms 860 KB Output is correct
20 Correct 2 ms 600 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 2 ms 756 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 3 ms 860 KB Output is correct
28 Correct 3 ms 856 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 2 ms 860 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 294 ms 40992 KB Output is correct
5 Correct 166 ms 31532 KB Output is correct
6 Correct 95 ms 30804 KB Output is correct
7 Correct 140 ms 31680 KB Output is correct
8 Correct 64 ms 27424 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 4 ms 860 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 3 ms 860 KB Output is correct
28 Correct 2 ms 600 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 1 ms 860 KB Output is correct
31 Correct 2 ms 756 KB Output is correct
32 Correct 1 ms 600 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 3 ms 860 KB Output is correct
36 Correct 3 ms 856 KB Output is correct
37 Correct 2 ms 860 KB Output is correct
38 Correct 1 ms 604 KB Output is correct
39 Correct 2 ms 860 KB Output is correct
40 Correct 338 ms 42876 KB Output is correct
41 Correct 197 ms 32528 KB Output is correct
42 Correct 234 ms 41780 KB Output is correct
43 Correct 226 ms 41748 KB Output is correct
44 Correct 112 ms 31768 KB Output is correct
45 Correct 113 ms 33828 KB Output is correct
46 Correct 69 ms 13220 KB Output is correct
47 Correct 196 ms 36940 KB Output is correct
48 Correct 136 ms 33540 KB Output is correct