Submission #519498

#	Time	Username	Problem	Language	Result	Execution time	Memory
519498		pokmui9909	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	35 / 100	1286 ms	123472 KiB

fortune_telling2

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

const ll S = (1 << 19);
struct MaxSegTree{
    ll T[2 * S] = {};
    void update(ll k, ll v) { update(1, 1, S, k, v); }
    ll query(ll l, ll r) { return query(1, 1, S, l, r); }
    void update(ll node, ll s, ll e, ll k, ll v){
        if (s == e){
            T[node] = max(T[node], v);
            return;
        }
        ll m = (s + e) / 2;
        ll lch = 2 * node, rch = 2 * node + 1;
        if (k <= m) update(lch, s, m, k, v);
        else update(rch, m + 1, e, k, v);
        ll x = T[lch], y = T[rch];
        T[node] = max(x, y);
    }
    ll query(ll node, ll s, ll e, ll l, ll r){
        if (e < l || s > r) return 0;
        if (l <= s && e <= r) return T[node];
        ll m = (s + e) / 2;
        ll lch = 2 * node, rch = 2 * node + 1;
        ll x = query(lch, s, m, l, r), y = query(rch, m + 1, e, l, r);
        return max(x, y);
    }
};
struct MergeSortTree{
    vector<ll> T[2 * S];
    ll query(ll l, ll r, ll k) {return query(1, 1, S / 2, l, r, k);}
    void init(){
        for(int i = S / 2 - 1; i >= 1; i--){
            vector<ll> &L = T[i * 2], &R = T[i * 2 + 1];
            T[i].resize(L.size() + R.size());
            merge(L.begin(), L.end(), R.begin(), R.end(), T[i].begin());
        }
    }
    void push(ll k, ll v){
        T[k + S / 2 - 1].push_back(v);
    }
    ll query(ll node, ll s, ll e, ll l, ll r, ll v){
        if(e < l || s > r) return 0;
        if(l <= s && e <= r) return T[node].end() - lower_bound(T[node].begin(), T[node].end(), v);
        ll m = (s + e) / 2, lch = node * 2, rch = node * 2 + 1;
        ll x = query(lch, s, m, l, r, v);
        ll y = query(rch, m + 1, e, l, r, v);
        return x + y;
    }
};
vector<ll> V;
map<ll, ll> mp;
MaxSegTree MT;
MergeSortTree SRT;
ll Index(ll n){
    return lower_bound(V.begin(), V.end(), n) - V.begin() + 1;
}
ll N, K;
ll A[200005];
ll B[200005];
ll Q[200005];
  
int main(){
    cin.tie(0) -> sync_with_stdio(false);
  
    cin >> N >> K;
    for(int i = 1; i <= N; i++){
        cin >> A[i] >> B[i];
        V.push_back(A[i]); V.push_back(B[i]);
    }
    for(int i = 1; i <= K; i++){
        cin >> Q[i];
        V.push_back(Q[i]);
    }
    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());
    for(int i = 1; i <= N; i++){
        mp[Index(A[i])] = A[i];
        A[i] = Index(A[i]);
        mp[Index(B[i])] = B[i];
        B[i] = Index(B[i]);
    }
    for(int i = 1; i <= K; i++){
        mp[Index(Q[i])] = Q[i];
        Q[i] = Index(Q[i]);
        MT.update(Q[i], i);
        SRT.push(i, Q[i]);
    }
    SRT.init();
    ll ans = 0;
    for(int i = 1; i <= N; i++){
        ll C = min(A[i], B[i]), D = max(A[i], B[i]);
        ll Last = MT.query(C, D - 1);
        ll R = SRT.query(Last + 1, K, D);
        if(Last == 0) C = B[i], D = A[i];
        if(R % 2 == 0){
            ans += mp[D];
        } else {
            ans += mp[C];
        }
    }
    cout << ans;
}   

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