Submission #411436

#	Time	Username	Problem	Language	Result	Execution time	Memory
411436		SolarSystem	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	2636 ms	80424 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

using ll           = long long;
using ld           = long double;
using pii          = pair<int, int>;
using pll          = pair<long, long>;
using vi           = vector<int>;
using vl           = vector<long long>;

#define pb             push_back
#define F              first
#define S              second
#define sz(a)          int((a).size())
#define all(a)         (a).begin(), (a).end()
#define rall(a)        (a).rbegin(), (a).rend()
#define sum(a)         ( accumulate((a).begin(), (a).end(), 0LL))
#define lowb(a, x)     ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x)     ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define yes            cout << "YES" << endl
#define no             cout << "NO"  << endl

void fastIO() { ios_base::sync_with_stdio(false); cin.tie(NULL); }

const ll mod = 1e9 + 7;

struct WaveletTree {
    vi b;
    int lo, hi;
    WaveletTree *l, *r;

    WaveletTree (int *i, int *j, int x, int y) {
        lo = x, hi = y;
        if (lo == hi) return;

        int mid = (lo + hi) / 2;
        b.pb(0);
        for (auto it = i; it != j; it++) {
            b.pb(b.back() + (*it <= mid));
        }

        auto k = stable_partition(i, j, [mid] (int x) {return x <= mid;});

        if (i < k) l = new WaveletTree(i, k, lo, mid);
        if (k < j) r = new WaveletTree(k, j, mid + 1, hi);
    }

    int query(int l, int r, int k) {
        if (l > r || k < lo) return 0;
        if (hi <= k) return r - l + 1;

        int lb = b[l - 1], rb = b[r];
        return this->l->query(lb + 1, rb, k) + this->r->query(l - lb, r - rb, k);
    }

    int query(int l, int r, int x, int y) {
        l++; r++;

        if (y < x) return 0;
        return query(l, r, y) - query(l, r, x - 1);
    }
};

void solve() {
    int n, k;
    cin >> n >> k;

    vi a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }

    int t[k];
    for (int &u: t) cin >> u;

    vi c;
    for (int u: a) c.pb(u);
    for (int u: b) c.pb(u);
    for (int u: t) c.pb(u);

    sort(all(c));
    c.resize(unique(all(c)) - c.begin());
    for (int &u: a) {
        u = lowb(c, u);
    }
    for (int &u: b) {
        u = lowb(c, u);
    }
    for (int &u: t) {
        u = lowb(c, u);
    }

    WaveletTree T(t, t + k, 0, 6e5);

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int x = T.query(0, k - 1, min(a[i], b[i]), max(a[i], b[i]) - 1);

        if (x == 0) {
            if (T.query(0, k - 1, max(a[i], b[i]), 1e9) % 2) {
                ans += c[b[i]];
            } else {
                ans += c[a[i]];
            }
        } else {
            int l = -1, r = k - 1;

            while (l + 1 < r) {
                int m = (l + r) / 2;

                if (T.query(0, m, min(a[i], b[i]), max(a[i], b[i]) - 1) == x) {
                    r = m;
                } else {
                    l = m;
                }
            }

            if (T.query(r + 1, k - 1, max(a[i], b[i]), 1e9) % 2) {
                ans += c[min(a[i], b[i])];
            } else {
                ans += c[max(a[i], b[i])];
            }
        }
    }

    cout << ans;
}

int main() {
    fastIO();

    cout << setprecision(15) << fixed;

    int t = 1;
    // cin >> t;

    while (t--) solve();

    return 0;
}

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