Submission #169248

#	Time	Username	Problem	Language	Result	Execution time	Memory
169248		wolfris	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	4 / 100	131 ms	3196 KiB

fortune_telling2

#include <iostream>
#include <algorithm>

using namespace std;

int n, k, a[200015], b[200015], g[200015], c[200015], x[200015], cnt[200015], BIT[200015], IT[1000015];

int getnum(int x) {
    int res = 0;
    for (x = upper_bound(c + 1, c + k + 1, x) - c; x <= k; x += x & -x)
        res += BIT[x];
    return res;
}

void addup(int x) {
    for (x = lower_bound(c + 1, c + k + 1, x) - c; x >= 1; x -= x & -x)
        ++BIT[x];
}

void update(int x, int p, int k, int l, int r) {
    if (x < c[l] || c[r] < x) return;
    IT[k] = max(IT[k], p);
    if (l < r)
        update(x, p, 2 * k, l, (l + r) / 2),
        update(x, p, 2 * k + 1, (l + r) / 2 + 1, r);
}

int getpos(int a, int b, int k, int l, int r) {
    if (b < c[l] || c[r] < a) return 0;
    if (a <= c[l] && c[r] <= b) return IT[k];
    return max(getpos(a, b, 2 * k, l, (l + r) / 2), getpos(a, b, 2 * k + 1, (l + r) / 2 + 1, r));
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        if (a[i] > b[i])
            swap(a[i], b[i]),
            g[i] = 1;
    }
    for (int i = 1; i <= k; ++i)
        cin >> x[i], c[i] = x[i];
    sort(c + 1, c + k + 1);
    for (int i = k; i >= 1; --i)
        cnt[i] = getnum(x[i]), addup(x[i]),
        update(x[i], i, 1, 1, k);
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        int p = getpos(a[i], b[i] - 1, 1, 1, k);
        if (p) {
            if (cnt[p] & 1) res += a[i];
            else res += b[i];
        }
        else {
            if (getnum(b[i]) & 1) {
                if (g[i]) res += a[i];
                else res += b[i];
            }
            else {
                if (g[i]) res += b[i];
                else res += a[i];
            }
        }
    }
    cout << res;
}

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