Submission #1147035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147035		VMaksimoski008	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	892 ms	169148 KiB

fortune_telling2

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 1e5 + 5;

struct persistent_sgt {
    struct node {
        int sum = 0;
        node *l, *r;

        node(int _s=0) : sum(_s), l(nullptr), r(nullptr) {}
        node(node *l, node *r) : l(l), r(r) {
            if(l) sum += l->sum;
            if(r) sum += r->sum;
        }
    };

    int n;
    vector<node*> R;
    persistent_sgt(int _n) : n(_n) {
        R.push_back(build(1, n));
    }

    node* build(int l, int r) {
        if(l == r) return new node();
        int m = (l + r) / 2;
        return new node(build(l, m), build(m+1, r));
    }

    node *update(node *u, int tl, int tr, int p) {
        if(tl == tr) return new node(1);
        int tm = (tl + tr) / 2;
        if(p <= tm) return new node(update(u->l, tl, tm, p), u->r);
        return new node(u->l, update(u->r, tm+1, tr, p));
    }

    int find(node *u, node *v, int tl, int tr) {
        if(u->sum - v->sum == 0) return 0;
        if(tl == tr) return tl;
        int tm = (tl + tr) / 2;
        if(u->r->sum - v->r->sum > 0) return find(u->r, v->r, tm+1, tr);
        return find(u->l, v->l, tl, tm);
    }

    int query(node *u, int tl, int tr, int l, int r) {
        if(tl > r || l > tr) return 0;
        if(l <= tl && tr <= r) return u->sum;
        int tm = (tl + tr) / 2;
        return query(u->l, tl, tm, l, r) + query(u->r, tm+1, tr, l, r);
    }

    int find(int x, int y) {
        return find(R[x], R[y], 1, n);
    }

    void update(int p) {
        R.push_back(update(R.back(), 1, n, p));
    }

    int query(int u, int l, int r) {
        return query(R[u], 1, n, l, r);
    }
};

bool cmp(int x, int y) {
    return x >= y;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, q; cin >> n >> q;
    vector<int> a(n+1), b(n+1);
    set<int> st;
    st.insert(0); st.insert(2e9);

    for(int i=1; i<=n; i++) {
        cin >> a[i] >> b[i];
        st.insert(a[i]);
        st.insert(b[i]);
    }

    vector<int> vec(st.begin(), st.end());

    vector<pii> qus;
    for(int i=1; i<=q; i++) {
        int x; cin >> x;
        qus.push_back({ x, i });
        st.insert(x);
    }

    vector<int> comp(st.begin(), st.end());
    sort(qus.rbegin(), qus.rend());
    sort(vec.rbegin(), vec.rend());

    int m = comp.size(), k = vec.size();
    persistent_sgt psgt(q);

    vector<int> sz(k);
    int j = 0;

    for(int i=0; i<k; i++) {
        while(j < qus.size() && qus[j].first >= vec[i]) {
            psgt.update(qus[j].second);
            j++;
        }

        sz[i] = psgt.R.size();
    }

    vector<int> pos(n+1);
    for(int i=1; i<=n; i++) {
        if(a[i] == b[i]) continue;
        int L = min(a[i], b[i]), R = max(a[i], b[i]);
        L = lower_bound(vec.begin(), vec.end(), L, cmp) - vec.begin();
        R = lower_bound(vec.begin(), vec.end(), R, cmp) - vec.begin();
        pos[i] = psgt.find(sz[L-1]-1, sz[R-1]-1);
    }

    for(int i=1; i<=n; i++) {
        if(a[i] == b[i]) continue;
        if(pos[i] && a[i] < b[i]) swap(a[i], b[i]);
        if(pos[i] == q) continue;
        // cout << i << ": " << a[i] << " " << b[i] << '\n';
        int p = lower_bound(vec.begin(), vec.end(), max(a[i], b[i]), cmp) - vec.begin();
        int cnt = psgt.query(sz[p-1]-1, pos[i]+1, q);
        // cout << i << ": " << cnt << '\n';
        if(cnt & 1) swap(a[i], b[i]); 
    }

    ll ans = 0;
    for(int i=1; i<=n; i++) ans += a[i];
    cout << ans << '\n';
}

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