Submission #1128010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128010		Zero_OP	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	In queue	0 ms	0 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        }
        return false;
    }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;

const int MAX = 2e5 + 5;

int N, Q, A[MAX], B[MAX], T[MAX];
vector<int> st[MAX << 2];

template<typename T>
void merge_sort(vector<T>& result, vector<T>& a, vector<T>& b){
    int i = 0, j = 0;
    while(i < sz(a) || j < sz(b)){
        if(i == sz(a)) result.push_back(b[j++]);
        else if(j == sz(b)) result.push_back(a[i++]);
        else if(a[i] < b[j]) result.push_back(a[i++]);
        else result.push_back(b[j++]);
    }
}

void build(int id, int l, int r){
    if(l == r){
        st[id] = {T[l]};
    } else{
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        merge_sort(st[id], st[id << 1], st[id << 1 | 1]);
    }
}

bool exist(int id, int lv, int rv){
    return upper_bound(all(st[id]), rv) != lower_bound(all(st[id]), lv);
}

int find_last(int id, int l, int r, int lv, int rv){
    if(l == r) return l;
    int mid = l + r >> 1;
    if(exist(id << 1 | 1, lv, rv)) return find_last(id << 1 | 1, mid + 1, r, lv, rv);
    else return find_last(id << 1, l, mid, lv, rv);
}

int find_last(int lv, int rv){
    if(exist(1, lv, rv)) return find_last(1, 1, Q, lv, rv);
    else return -1;
}

int calc(int id, int lv){
    return st[id].end() - lower_bound(all(st[id]), lv);
}

int count_bound(int id, int l, int r, int u, int v, int lv){
    if(u <= l && r <= v){
        return calc(id, lv);
    }

    int mid = l + r >> 1;
    if(u > mid) return count_bound(id << 1 | 1, mid + 1, r, u, v, lv);
    if(mid >= v) return count_bound(id << 1, l, mid, u, v, lv);
    return count_bound(id << 1, l, mid, u, v, lv) + count_bound(id << 1 | 1, mid + 1, r, u, v, lv);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    file("task");

    cin >> N >> Q;
    for(int i = 1; i <= N; ++i) cin >> A[i] >> B[i];
    for(int i = 1; i <= Q; ++i) cin >> T[i];

    build(1, 1, Q);

    ll ans = 0;
    for(int i = 1; i <= N; ++i){

        if(A[i] == B[i]){
            ans += A[i];
            continue;
        }

        if(A[i] < B[i]){
            int last = find_last(A[i], B[i] - 1);
            if(last == -1){
                int both = count_bound(1, 1, Q, 1, Q, B[i]);
                //still at A[i]
                if(both & 1){
                    ans += B[i];
                } else{
                    ans += A[i];
                }
            } else{
                int both = count_bound(1, 1, Q, last, Q, B[i]);
                //at B[i] now
                if(both & 1){
                    ans += A[i];
                } else{
                    ans += B[i];
                }
            }
        } else{
            swap(A[i], B[i]);
            int last = find_last(A[i], B[i] - 1);
            if(last == -1){
                int both = count_bound(1, 1, Q, 1, Q, B[i]);
                //currently at B[i]
                if(both & 1){
                    ans += A[i];
                } else{
                    ans += B[i];
                }
            } else{
                int both = count_bound(1, 1, Q, last, Q, B[i]);
                //still at B[i]
                if(both & 1){
                    ans += A[i];
                } else{
                    ans += B[i];
                }
            }
        }
    }

    cout << ans << '\n';

    return 0;
}