Submission #1270434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270434		huydayy	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	0 / 100	1 ms	320 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SegTree {
    int n;
    vector<int> st;
    SegTree(int _n=0){ init(_n); }
    void init(int _n){
        n = 1; while(n < _n) n <<= 1;
        st.assign(2*n, 0);
    }
    void build(const vector<int>& a){
        int m = (int)a.size();
        init(m);
        for(int i=0;i<m;i++) st[n+i] = a[i];
        for(int i=n-1;i>0;i--) st[i] = max(st[2*i], st[2*i+1]);
    }
    // query max on [l, r] inclusive
    int query(int l, int r){
        if(l>r) return 0;
        l += n; r += n;
        int res = 0;
        while(l <= r){
            if(l&1) res = max(res, st[l++]);
            if(!(r&1)) res = max(res, st[r--]);
            l >>= 1; r >>= 1;
        }
        return res;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if(!(cin >> n >> m)) return 0;
    vector<int> A(n), B(n);
    for(int i=0;i<n;i++) cin >> A[i] >> B[i];
    vector<int> T(m);
    for(int j=0;j<m;j++) cin >> T[j];

    // coordinate compress all A, B, T
    vector<int> vals;
    vals.reserve(n*2 + m);
    for(int x: A) vals.push_back(x);
    for(int x: B) vals.push_back(x);
    for(int x: T) vals.push_back(x);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    auto idx = [&](int x){
        return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin());
    };

    int V = (int)vals.size();
    // last occurrence index (1-based) for each compressed value
    vector<int> last(V, 0);
    for(int j=0;j<m;j++){
        int p = idx(T[j]);
        last[p] = j+1; // store 1-based index of last occurrence
    }

    SegTree seg;
    seg.build(last);

    ll ans = 0;
    for(int i=0;i<n;i++){
        int cur = A[i], other = B[i];
        int prev = 0; // last operation index we've used (1-based)
        while(true){
            if(cur == other) break;
            // decide interval depending on which side is currently shown
            int l = int(lower_bound(vals.begin(), vals.end(), cur) - vals.begin());
            int r;
            if(cur < other){
                // need T in [cur, other-1]
                r = int(lower_bound(vals.begin(), vals.end(), other) - vals.begin()) - 1;
            } else {
                // cur > other: need T >= cur
                r = V - 1;
            }
            if(l > r) break;
            int mx = seg.query(l, r); // last occurrence index (1-based) in that value-range
            if(mx <= prev) break; // no occurrence after prev
            prev = mx;
            swap(cur, other); // flip the shown face
        }
        ans += cur;
    }

    cout << ans << "\n";
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65