Submission #1264241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264241		buidangnguyen05	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	322 ms	20752 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 2e5 + 10;
int a[N], b[N];

struct SegmentTree {
    vector<int> T;

    SegmentTree(int n) {
        T.resize(4 * n + 1);
    }

    void up(int s, int l, int r, int x, int v) {
        if (l == r) {
            T[s] = v;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) up(s << 1, l, mid, x, v);
        else up(s << 1 | 1, mid + 1, r, x, v);
        T[s] = max(T[s << 1], T[s << 1 | 1]);
    }

    int get(int s, int l, int r, int u, int v) {
        if (l > v || r < u || u > v) return 0;
        if (l >= u && r <= v) return T[s];
        int mid = (l + r) >> 1;
        return max(get(s << 1, l, mid, u, v), get(s << 1 | 1, mid + 1, r, u, v));
    }
};

struct BinaryIndexedTree {
    vector<int> bit;
    int size;

    BinaryIndexedTree(int n) : size(n){
        bit.resize(n + 1);
    }

    void up(int x) {
        for (; x; x -= x & -x) ++bit[x];
    }
    
    int get(int x) {
        int res = 0;
        for (; x <= size; x += x & -x) res += bit[x];
        return res;
    }
};

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    #ifdef LOCAL_MACHINE
        if (fopen("task.inp", "r")) {
            freopen("task.inp", "r", stdin);
            freopen("task.out", "w", stdout);
        }
    #endif

    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
    vector<pair<int, int>> q;
    for (int i = 1; i <= k; ++i) {
        int x; cin >> x;
        q.emplace_back(x, i);
    }
    vector<int> comp;
    for (int i = 1; i <= n; ++i) {
        comp.push_back(a[i]);
        comp.push_back(b[i]);
    }
    for (int i = 1; i <= k; ++i) comp.push_back(q[i - 1].first);

    sort(all(comp));
    comp.resize(unique(all(comp)) - comp.begin());

    int m = comp.size();
    // find last card a <= t < b
    SegmentTree it(m);

    for (auto &[x, id] : q) {
        int p = upper_bound(all(comp), x) - comp.begin();
        it.up(1, 1, m, p, id);
    }

    vector<tuple<int, int, int>> qr;
    for (int i = 1; i <= n; ++i) {
        int l = upper_bound(all(comp), a[i]) - comp.begin();
        int r = upper_bound(all(comp), b[i]) - comp.begin();

        if (l > r) swap(l, r);
        qr.emplace_back(it.get(1, 1, m, l, r - 1), max(a[i], b[i]), i);
    }

    // count number of cards after last >= b
    sort(all(qr)); 
    reverse(all(q));
    BinaryIndexedTree bit(m);

    for (auto &[x, id] : q) {
        int p = upper_bound(all(comp), x) - comp.begin();
        bit.up(p);

        while (qr.size() && get<0>(qr.back()) == id) {
            auto [_, val, i] = qr.back(); qr.pop_back();
            int pos = upper_bound(all(comp), val) - comp.begin();
            int cnt = bit.get(pos);

            if (cnt & 1) {
                if (a[i] > b[i]) swap(a[i], b[i]);
            }
            else {
                if (a[i] < b[i]) swap(a[i], b[i]);
            }
        }
    }

    while (qr.size()) {
        auto [_, val, i] = qr.back(); qr.pop_back();
        int pos = upper_bound(all(comp), val) - comp.begin();
        int cnt = bit.get(pos);

        if (cnt & 1) swap(a[i], b[i]);
    }

    ll res = 0;
    for (int i = 1; i <= n; ++i) res += a[i];

    cout << res << "\n";
}

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