Submission #1100722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100722		vjudge1	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	233 ms	180400 KiB

fortune_telling2

#include <bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const ll maxn = 1e6 + 2, LG = 20, mod = 1e9 + 7, inf = 1e18;
ll n, m, k, a[maxn], b[maxn], t[maxn], fw[maxn], st[LG][maxn], res = 0;
vector<ll> v, events[maxn];
int rmq (int l, int r)
{
    if (l > r) return 0;
    int k = __lg(r - l + 1);
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}
void upd (int idx)
{
    while (idx <= m)
    {
        fw[idx]++;
        idx += (idx & (-idx));
    }
}
int get (int idx)
{
    int res = 0;
    while (idx > 0)
    {
        res += fw[idx];
        idx -= (idx & (-idx));
    }
    return res;
}
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    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 >> t[i];
        v.push_back(t[i]);
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    m = v.size();
    //for (int i : v) cout << i << " ";
    //cout << '\n';
    for (int i = 1; i <= n; i++)
    {
        //cout << "before " << a[i] << " " << b[i] << '\n';
        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;
        //cout << "after " << a[i] << " " << b[i] << '\n';
    }
    for (int i = 1; i <= k; i++)
    {
        t[i] = lower_bound(v.begin(), v.end(), t[i]) - v.begin() + 1;
        st[0][t[i]] = i;
    }
    for (int j = 1; j < LG; j++)
        for (int i = 1; i <= m - (1 << (j - 1)); i++)
            st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
    for (int i = 1; i <= n; i++)
        events[rmq(min(a[i], b[i]), max(a[i], b[i]) - 1)].push_back(i);
    for (int i = k; i >= 0; i--)
    {
        for (int j : events[i])
        {
            if (i != 0)
            {
                if (a[j] < b[j]) swap(a[j], b[j]);
            }
            ll debug;
            res += (debug = (((get(m) - get(max(a[j], b[j]) - 1)) & 1) ? v[b[j] - 1] : v[a[j] - 1]));
            //cout << i << " " << j << " " << v[a[j] - 1] << " " << v[b[j] - 1] << " " << debug << '\n';
        }
        if (i != 0) upd(t[i]);
    }
    cout << res;
}

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