Submission #1112212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112212		ortsac	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	325 ms	27476 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second

const int MAXN = 2e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;

struct Node {
    int mi = INF, mx = -INF;
    int qtdmx = 0;
};

Node merge(const Node& a, const Node& b) {
    Node ans;
    ans.mi = min(a.mi, b.mi);
    ans.mx = max(a.mx, b.mx);
    if (ans.mx == a.mx) ans.qtdmx += a.qtdmx;
    if (ans.mx == b.mx) ans.qtdmx += b.qtdmx;
    return ans;
}

Node seg[4*MAXN];
int v[MAXN];

void build(int node, int l, int r) {
    if (l == r) {
        seg[node].mi = seg[node].mx = v[l];
        seg[node].qtdmx = 1;
        return;
    }
    int m = (l+r)/2;
    build(2*node, l, m);
    build(2*node + 1, m + 1, r);
    seg[node] = merge(seg[2*node], seg[2*node + 1]);
}

// find last value that is smaller than x
int bsearch(int node, int l, int r, int x) {
    //////cout << "hey search here " << l << " " << r << "\n";
    if (l == r) {
        if (seg[node].mi < x)
            return l;
        else
            return 0;
    }
    int m = (l+r)/2;
    if (seg[2*node + 1].mi < x) return bsearch(2*node + 1, m + 1, r, x);
    else if (seg[2*node].mi < x) return bsearch(2*node, l, m, x);
    else return 0;
}

void update(int node, int l, int r, int po) {
    if (l == r) {
        seg[node].mi = seg[node].mx = INF;
        return;
    }
    int m = (l+r)/2;
    if (po <= m) update(2*node, l, m, po);
    else update(2*node + 1, m + 1, r, po);
    seg[node] = merge(seg[2*node], seg[2*node + 1]);
}

Node empt;

Node query(int node, int l, int r, int tl, int tr) {
    ////cout << "query " << l << " " << r << " " << node << "\n";
    if ((tr < l) || (r < tl)) return empt;
    if ((tl <= l) && (r <= tr)) return seg[node];
    int m = (l+r)/2;
    return merge(query(2*node, l, m, tl, tr), query(2*node + 1, m + 1, r, tl, tr));
}

bool comp(pii a, pii b) {
    return (min(a.fr, a.se) < min(b.fr, b.se));
}

int32_t main() {
    int n, k;
    cin >> n >> k;
    vector<pii> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i].fr >> c[i].se;
    }
    vector<pii> po;
    for (int i = 1; i <= k; i++) {
        cin >> v[i];
        po.push_back({v[i], i});
    }
    sort(po.begin(), po.end(), greater<pii>());
    sort(c.begin(), c.end(), comp);
    build(1, 1, k);
    int ans = 0;
    for (auto& u : c) {
        if (u.fr == u.se) {
            ans += u.fr;
            //cout << u.fr << " " << u.se << " " << u.fr << "\n";
            continue;
        }
        while ((!po.empty()) && (po.back().fr < min(u.fr, u.se))) {
            //cout << "rem " << po.back().fr << " " << po.back().se << "\n";
            update(1, 1, k, po.back().se);
            ////cout << seg[1].mx << "\n";
            po.pop_back();
        }
        if (po.empty()) {
            ans += u.fr;
            //cout << u.fr << " " << u.se << " " << u.fr << "\n";
            continue;
        }
        if (u.fr < u.se) {
            int p = bsearch(1, 1, k, u.se);
            if (p == k) {
                ans += u.se;
                //cout << u.fr << " " << u.se << " " << u.se << "\n";
                continue;
            }
            int comeco = 0;
            int qtd = (k - p);
            Node q = query(1, 1, k, p + 1, k);
            ////cout << q.mi << " " << q.mx << " " << q.qtdmx << "\n";
            if (q.mx == INF) qtd -= q.qtdmx;
            if (p == 0) {
                comeco = 1;
            }
            qtd += comeco;
            ////cout << qtd << " " << comeco << " " << p << "\n";
            if ((qtd % 2LL) == 1LL) {
                ans += u.fr;
                //cout << u.fr << " " << u.se << " " << u.fr << "\n";
            }
            else {
                ans += u.se;
                //cout << u.fr << " " << u.se << " " << u.se << "\n";
            }
            continue;
        } else {
            swap(u.fr, u.se);
            int p = bsearch(1, 1, k, u.se);
            if (p == k) {
                ans += u.se;
                //cout << u.se << " " << u.fr << " " << u.se << "\n";
                continue;
            }
            int comeco = 0;
            int qtd = (k - p);
            Node q = query(1, 1, k, p + 1, k);
            if (q.mx == INF) qtd -= q.qtdmx;
            //if (p == 0) {
            //    comeco = 1;
            //}
            //cout << qtd << " " << p << "\n";
            qtd += comeco;
            if ((qtd % 2LL) == 1LL) {
                ans += u.fr;
                //cout << u.se << " " << u.fr << " " << u.fr << "\n";
            }
            else {
                ans += u.se;
                //cout << u.se << " " << u.fr << " " << u.se << "\n";
            }
            continue;
        }
    }
    cout << ans << "\n";
}
// 3 2 2
// 4 5 5

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