Submission #1035257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035257		GasmaskChan	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	336 ms	54708 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define MAX 200001

int a[MAX], b[MAX], q[MAX];

struct Seg
{
    int n;
    vector<int> ST;

    Seg(int _n) : n(_n)
    {
        ST.assign(1 << (__lg(_n) + 2), -1);
    }

    void update(int pos, int val)
    {
        int mid, id = 1, l = 1, r = n;
        while (l < r)
        {
            mid = (l + r) >> 1;
            if (pos > mid) id = id << 1 | 1, l = mid + 1;
            else id <<= 1, r = mid;
        }

        ST[id] = val;

        while (id > 1)
        {
            id >>= 1;
            ST[id] = max(ST[id << 1], ST[id << 1 | 1]);
        }
    }

    int getpos(int id, int l, int r, int u, int v)
    {
        if (r < u || v < l) return -1;
        if (u <= l && r <= v) return ST[id];
        int mid = (l + r) >> 1;

        return max(getpos(id << 1, l, mid, u, v), getpos(id << 1 | 1, mid + 1, r, u, v));
    }

    int getpos(int u, int v)
    {
        return getpos(1, 1, n, u, v);
    }
};

struct waifutree
{
    int n;
    vector<int> BIT;

    waifutree(int _n) : n(_n)
    {
        BIT.assign(_n + 1, 0);
    }

    void update(int i, int val)
    {
        for (; i <= n; i += -i & i) BIT[i] += val;
    }

    int get(int i)
    {
        int res = 0;
        for (; i > 0; i -= -i & i) res += BIT[i];
        return res;
    }
};

vector<int> v, res[2 * MAX + MAX], nopar;
bool check[2 * MAX + MAX];
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("ilight.inp", "r", stdin); freopen("ilight.out", "w", stdout);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i], v.push_back(a[i]), v.push_back(b[i]);
    for (int i = 1; i <= k; i++) cin >> q[i], v.push_back(q[i]);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    Seg sg(n * 2 + k);
    waifutree fw(n * 2 + k);
    for (int i = 1; i <= k; i++)
    {
        q[i] = lower_bound(v.begin(), v.end(), q[i]) - v.begin() + 1;
        sg.update(q[i], i);
    }

    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
        b[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin() + 1;
        int j = sg.getpos(min(a[i], b[i]), max(a[i], b[i]) - 1);

        if (j != -1) res[q[j]].push_back(i);
        else nopar.push_back(i);
    }

    int ans = 0;
    for (int i = k; i > 0; i--)
    {
        if (!check[q[i]])
        {
            check[q[i]] = true;
            for (int j : res[q[i]])
            {
                int t = fw.get(n * 2 + k) - fw.get(max(a[j], b[j]) - 1);
                if (a[j] <= b[j])
                {
                    if (t & 1) ans += v[a[j] - 1];
                    else ans += v[b[j] - 1];
                }
                else
                {
                    if (t & 1) ans += v[b[j] - 1];
                    else ans += v[a[j] - 1];
                }
            }
        }
        fw.update(q[i], 1);
    }

    for (int i : nopar)
    {
        int j = fw.get(n * 2 + k) - fw.get(max(a[i], b[i]) - 1);
        if (j == 0)
        {
            ans += v[a[i] - 1];
            continue;
        }
        if (j & 1) ans += v[b[i] - 1];
        else ans += v[a[i] - 1];
    }

    cout << ans;
    return 0;
}

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