Submission #113574

#	Time	Username	Problem	Language	Result	Execution time	Memory
113574		popovicirobert	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	307 ms	16552 KiB

fortune_telling2

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

struct SegTree {

    struct Node {
        int cnt;
        int mx;
    };

    vector <Node> aint;
    int n;

    inline void init(int _n) {
        n = _n;
        aint.resize(4 * n + 1, {0, 0});
    }

    inline void refresh(int nod) {
        aint[nod].cnt = aint[2 * nod].cnt + aint[2 * nod + 1].cnt;
        aint[nod].mx = max(aint[2 * nod].mx, aint[2 * nod + 1].mx);
    }

    void update_cnt(int nod, int left, int right, int pos) {
        if(left == right) {
            aint[nod].cnt++;
        }
        else {
            int mid = (left + right) / 2;

            if(pos <= mid) update_cnt(2 * nod, left, mid, pos);
            else update_cnt(2 * nod + 1, mid + 1, right, pos);

            refresh(nod);
        }
    }

    void update_mx(int nod, int left, int right, int pos, int mx) {
        if(left == right) {
            aint[nod].mx = mx;
        }
        else {
            int mid = (left + right) / 2;

            if(pos <= mid) update_mx(2 * nod, left, mid, pos, mx);
            else update_mx(2 * nod + 1, mid + 1, right, pos, mx);

            refresh(nod);
        }
    }

    int query_mx(int nod, int left, int right, int val) {

        if(aint[nod].mx < val) {
            return 0;
        }

        if(left == right) {
            return left;
        }
        else {
            int mid = (left + right) / 2;

            if(aint[2 * nod + 1].mx >= val) return query_mx(2 * nod + 1, mid + 1, right, val);
            return query_mx(2 * nod, left, mid, val);
        }
    }

    int query_cnt(int nod, int left, int right, int l, int r) {

        if(l > r) return 0;

        if(l <= left && right <= r) {
            return aint[nod].cnt;
        }
        else {
            int mid = (left + right) / 2;
            int ans = 0;

            if(l <= mid) ans += query_cnt(2 * nod, left, mid, l, r);
            if(mid < r) ans += query_cnt(2 * nod + 1, mid + 1, right, l, r);

            return ans;
        }
    }

};


int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    vector <int> ord(n + 1), a(n + 1), b(n + 1);

    for(i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        ord[i] = i;
    }

    sort(next(ord.begin()), ord.end(), [&](const int &x, const int &y) {

            return max(a[x], b[x]) > max(a[y], b[y]);

         });

    vector < pair <int, int> > t(m + 1);

    for(i = 1; i <= m; i++) {
        cin >> t[i].first;
        t[i].second = i;
    }

    sort(next(t.begin()), t.end(), [&](const pair <int, int> &a, const pair <int, int> &b) {

            return a.first > b.first;

         });

    SegTree st; st.init(m);

    for(i = 1; i <= m; i++) {
        st.update_mx(1, 1, m, t[i].second, t[i].first);
    }

    ll ans = 0;
    int pos = 1;

    for(i = 1; i <= n; i++) {
        while(pos <= m && t[pos].first >= max(a[ord[i]], b[ord[i]])) {
            st.update_cnt(1, 1, m, t[pos].second);
            st.update_mx(1, 1, m, t[pos].second, 0);
            pos++;
        }

        int p = st.query_mx(1, 1, m, min(a[ord[i]], b[ord[i]]));

        if(p != 0) {
            if(a[ord[i]] < b[ord[i]]) {
                swap(a[ord[i]], b[ord[i]]);
            }
        }

        if(st.query_cnt(1, 1, m, p + 1, m) % 2) {
            ans += b[ord[i]];
        }
        else {
            ans += a[ord[i]];
        }

    }

    cout << ans;

    //cin.close();
    //cout.close();
    return 0;
}

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