제출 #1270433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270433		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]);
    }

    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];

    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();
    vector<int> last(V, 0);
    for(int j=0;j<m;j++){
        int p = idx(T[j]);
        last[p] = j+1; 
    }

    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;
        while(true){
            if(cur == other) break;
            int low = min(cur, other);
            int high = max(cur, other);
            int l = int(lower_bound(vals.begin(), vals.end(), low) - vals.begin());
            int r = int(lower_bound(vals.begin(), vals.end(), high) - vals.begin()) - 1;
            if(l > r){ 
                break;
            }
            int mx = seg.query(l, r); 
            if(mx <= prev) break; 
            prev = mx;
            swap(cur, other); 
        }
        ans += cur;
    }

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

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