Submission #1274863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274863		reginox	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	227 ms	25164 KiB

fortune_telling2

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
struct BIT {
    int n;
    vector<int> bit;
    BIT(int n=0): n(n), bit(n+1, 0) {}
    void add(int i, int v = 1) { for (; i <= n; i += i & -i) bit[i] += v; }
    int sum(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }
};
struct Seg {
    int n;
    vector<int> seg;
    Seg(int m = 0) { init(m); }
    void init(int m) {
        n = 1;
        while (n < m) n <<= 1;
        seg.assign(2*n, 0);
    }
    void set_leaf(int idx, int val) {
        int p = idx + n;
        seg[p] = val;
        for (p >>= 1; p; p >>= 1) seg[p] = max(seg[p<<1], seg[p<<1|1]);
    }
    int range_max(int l, int r) {
        if (l > r) return 0;
        l += n; r += n;
        int res = 0;
        while (l <= r) {
            if (l & 1) res = max(res, seg[l++]);
            if (!(r & 1)) res = max(res, seg[r--]);
            l >>= 1; r >>= 1;
        }
        return res;
    }
};
struct Query {
    ll L;
    int pos;
    int id;
    bool hasM;
    ll s, l;
    ll orig;
};
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k; cin>>n>>k;
    vector<ll> a(n+1), b(n+1);
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
    vector<ll> t(k+1);
    for (int j = 1; j <= k; ++j) cin >> t[j];
    vector<ll> vals;
    vals.reserve(k);
    for (int j = 1; j <= k; ++j) vals.push_back(t[j]);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int m = (int)vals.size();
    vector<int> lastPos(m, 0);
    for (int j = 1; j <= k; ++j) {
        int idx = int(lower_bound(vals.begin(), vals.end(), t[j]) - vals.begin());
        lastPos[idx] = max(lastPos[idx], j);
    }
    Seg st(m);
    for (int i = 0; i < m; ++i) st.set_leaf(i, lastPos[i]);
    vector<Query> qs; 
    for (int i = 1; i <= n; ++i) {
        ll s = min(a[i], b[i]);
        ll l = max(a[i], b[i]);
        int lo = int(lower_bound(vals.begin(), vals.end(), s) - vals.begin());
        int hi = int(upper_bound(vals.begin(), vals.end(), l - 1) - vals.begin()) - 1;
        int lastM = 0;
        bool hasM = false;
        if (lo <= hi && lo < m && hi >= 0) {
            lastM = st.range_max(max(0, lo), min(m-1, hi));
            if (lastM > 0) hasM = true;
        }
        int pos = hasM ? lastM : 0;
        qs.push_back({l, pos, i, hasM, s, l, a[i]});
    }
    vector<pair<ll,int>> ops;
    ops.reserve(k);
    for (int j = 1; j <= k; ++j) ops.emplace_back(t[j], j);
    sort(ops.begin(), ops.end(), greater<>());
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int x, int y) {
        if (qs[x].L != qs[y].L) return qs[x].L > qs[y].L;
        return qs[x].pos < qs[y].pos;
    });
    BIT bit(k);
    ll added = 0;
    int p = 0;
    vector<ll> cntAfter(n+1, 0);
    for (int idx : order) {
        ll need = qs[idx].L;
        while (p < (int)ops.size() && ops[p].first >= need) {
            bit.add(ops[p].second, 1);
            ++added;
            ++p;
        }
        int jpos = qs[idx].pos;
        ll cnt = added - bit.sum(jpos);
        cntAfter[qs[idx].id] = cnt;
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        auto &q = qs[i-1];
        ll s = q.s, l = q.l;
        ll cnt = cntAfter[i];
        ll finalv;
        if (q.hasM) finalv = (cnt % 2 == 0) ? l : s;
        else finalv = (cnt % 2 == 0) ? q.orig : ((q.orig == s) ? l : s);
        ans += finalv;
    }
    cout << ans;
    return 0;
}

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