Submission #1100898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100898		vjudge1	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	169 ms	8272 KiB

fortune_telling2

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxn = 2 * 1e5 + 7;
const int LOG = 31;
const long long MOD = (long long)(1e9) + 7;
const long long base = 311;
const int ALP_BET = 26;

typedef pair<int, int> ii;
typedef pair<int, long long> il;
typedef pair<long long, int> li;
typedef pair<long long, long long> ll;

int n, k;

ii a[maxn];

int t[maxn];

namespace SUB1 {

long long ans = 0;

void solve(){
    ans = 0;

    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= k; ++j) if(a[i].F <= t[j]){
            swap(a[i].F, a[i].S);
        }
        ans = ans + 1LL * a[i].F;
    }

    cout << ans << "\n";

    return;
}

};

namespace FULL{

struct Fenwick_Tree{
    int size;
    vector<int> sums;

    void init(int n){
        size = n;
        sums.assign(n + 7, 0);
        return;
    }

    void update(int id, int val){
        for(int i = id; i <= size; i = i | (i + 1)){
            sums[i] = sums[i] + val;
        }
        return;
    }

    int get_pre(int id){
        int res = 0;
        for(int i = id; i >= 1; i = (i & (i + 1)) - 1){
            res = res + sums[i];
        }
        return res;
    }

    int get_suffix(int id){
        int res = get_pre(k) - get_pre(id - 1);
        return res;
    }
};

struct SegTree{
    int size;
    vector<int> maxs;

    void init(int n){
        size = n;
        maxs.assign(n * 4 + 7, 0);
        return;
    }

    void update(int id, int l, int r, int u, int val){
        if(u < l || u > r)
            return;
        if(l == r){
            maxs[id] = max(maxs[id], val);
            return;
        }
        int mid = (l + r) / 2;
        update(id * 2, l, mid, u, val);
        update(id * 2 + 1, mid + 1, r, u, val);
        maxs[id] = max(maxs[id * 2], maxs[id * 2 + 1]);
        return;
    }

    void update(int id, int pos){
        update(1, 1, size, id, pos);
        return;
    }

    int get_max(int id, int l, int r, int u, int v){
        if(v < l || u > r)
            return 0;
        if(u <= l && r <= v){
            return maxs[id];
        }
        int mid = (l + r) / 2;
        return max(get_max(id * 2, l, mid, u, v), get_max(id * 2 + 1, mid + 1, r, u, v));
    }

    int get_max(int l, int r){
        return get_max(1, 1, size, l, r);
    }

};

bool cmp(ii a, ii b){
    return max(a.F, a.S) < max(b.F, b.S);
}

long long ans;

ii arr[maxn];

SegTree st;
Fenwick_Tree BIT;

void solve(){
    // INIT
    ans = 0;

    for(int i = 1; i <= k; ++i)
        arr[i] = {t[i], i};
    sort(arr + 1, arr + k + 1);

    sort(a + 1, a + n + 1, cmp);

    BIT.init(k);
    for(int i = 1; i <= k; ++i)
        BIT.update(i, 1);

    st.init(k);

    int id = 0;
    for(int i = 1; i <= n; ++i){
        if(a[i].F == a[i].S){
            ans = ans + 1LL * a[i].F;
            continue;
        }

        int val = max(a[i].F, a[i].S);
        while(id < k && val > arr[id + 1].F){
            ++id;
            int pos = arr[id].S;
            BIT.update(pos, -1);
            st.update(id, pos);
        }

        // CAL_ANS
        int LOW = min(a[i].F, a[i].S);
        int l = 1, r = id, res = -1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(arr[mid].F >= LOW){
                res = mid;
                r = mid - 1;
            } else
                l = mid + 1;
        }

        if(res == -1){
            int num = BIT.get_pre(k);
            if(num % 2 == 0)
                ans = ans + 1LL * a[i].F;
            else
                ans = ans + 1LL * a[i].S;
        } else{
            int pos = st.get_max(res, id);
            int num = BIT.get_suffix(pos + 1);
            if(a[i].F < a[i].S)
                swap(a[i].F, a[i].S);
            if(num % 2 == 0)
                ans = ans + 1LL * a[i].F;
            else
                ans = ans + 1LL * a[i].S;
        }

    }

    cout << ans << "\n";

    return;
}

}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> a[i].F >> a[i].S;

    for(int i = 1; i <= k; ++i)
        cin >> t[i];

//    SUB1::solve();

    FULL::solve();

    return 0;
}

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