Submission #1218599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218599		Double_Slash	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	342 ms	12512 KiB

fortune_telling2

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;

template <int (*COMB)(int, int)>
struct St {
    int n;
    vector<int> st;

    void init(int n) { st.resize((this->n = n) << 1); }

    void update(int i, int a, int b) {
        for ((st[i += n] *= a) += b; i >>= 1;) st[i] = COMB(st[i << 1], st[i << 1 | 1]);
    }

    int query(int l, int r) {
        int ret = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ret = COMB(ret, st[l++]);
            if (r & 1) ret = COMB(ret, st[--r]);
        }
        return ret;
    }
};
St<[] (int a, int b) { return max(a, b); }> mx;
St<[] (int a, int b) { return a + b; }> sum;

int main() {
    int n, q;
    cin >> n >> q;
    int A[n], B[n];
    for (int i = n; i--;) cin >> A[i] >> B[i];
    int ops[q];
    for (int &op: ops) cin >> op;
    vector<int> cc(ops, ops + q);
    sort(all(cc));
    cc.erase(unique(all(cc)), cc.end());
    mx.init(cc.size());
    auto idx = [&] (int i) { return lower_bound(all(cc), i) - cc.begin(); };
    for (int i = 0; i < q; ++i) mx.update(idx(ops[i]), 0, i + 1);
    vector<int> queries[q + 1];
    for (int i = n; i--;) {
        int j = mx.query(idx(min(A[i], B[i])), idx(max(A[i], B[i])));
        if (j and A[i] < B[i]) swap(A[i], B[i]);
        queries[j].emplace_back(i);
    }
    sum.init(cc.size());
    ll ans = 0;
    for (int i = q; i >= 0; --i) {
        if (i < q) sum.update(idx(ops[i]), 1, 1);
        for (int j: queries[i]) ans += sum.query(idx(max(A[j], B[j])), cc.size()) & 1 ? B[j] : A[j];
    }
    cout << ans << endl;
}

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