Submission #584825

#	Time	Username	Problem	Language	Result	Execution time	Memory
584825		Hanksburger	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	1197 ms	85288 KiB

fortune_telling2

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[200005], b[200005], t[200005];
vector<int> s[800005];
map<int, int> mp;
void f(int i, int l, int r)
{
    sort(s[i].begin(), s[i].end());
    if (l<r)
    {
        int mid=(l+r)/2;
        f(i*2, l, mid);
        f(i*2+1, mid+1, r);
    }
}
void upd(int i, int l, int r, int q, int x)
{
    s[i].push_back(x);
    if (l<r)
    {
        int mid=(l+r)/2;
        if (l<=q && q<=mid)
            upd(i*2, l, mid, q, x);
        else
            upd(i*2+1, mid+1, r, q, x);
    }
}
int queMax(int i, int l, int r, int ql, int qr)
{
    if (ql<=l && r<qr)
    {
        if (s[i].empty())
            return 0;
        return s[i][s[i].size()-1];
    }
    int mid=(l+r)/2, res=0;
    if (ql<=mid && l<qr)
        res=max(res, queMax(i*2, l, mid, ql, qr));
    if (ql<=r && mid+1<qr)
        res=max(res, queMax(i*2+1, mid+1, r, ql, qr));
    return res;
}
int queCnt(int i, int l, int r, int q, int x)
{
    if (q<=l)
    {
        int ind=upper_bound(s[i].begin(), s[i].end(), x)-s[i].begin();
        return s[i].size()-ind;
    }
    int mid=(l+r)/2, res=0;
    if (q<=mid)
        res+=queCnt(i*2, l, mid, q, x);
    if (q<=r)
        res+=queCnt(i*2+1, mid+1, r, q, x);
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q, sz=0, ans=0;
    cin >> n >> q;
    for (int i=1; i<=n; i++)
        cin >> a[i] >> b[i];
    for (int i=1; i<=q; i++)
    {
        cin >> t[i];
        mp[t[i]]=1;
    }
    for (auto itr=mp.begin(); itr!=mp.end(); itr++)
    {
        sz++;
        itr->second=sz;
    }
    for (int i=1; i<=q; i++)
        upd(1, 1, sz, mp[t[i]], i);
    f(1, 1, sz);
    for (int i=1; i<=n; i++)
    {
        auto itr1=mp.lower_bound(a[i]), itr2=mp.lower_bound(b[i]);
        int x=(itr1==mp.end()?1e9:itr1->second), y=(itr2==mp.end()?1e9:itr2->second);
        if (x>y)
            swap(x, y);
        int res1=queMax(1, 1, sz, x, y);
        int res2=queCnt(1, 1, sz, y, res1);
        if (!res1)
        {
            if (res2&1)
                ans+=b[i];
            else
                ans+=a[i];
        }
        else
        {
            if (res2&1)
                ans+=min(a[i], b[i]);
            else
                ans+=max(a[i], b[i]);
        }
    }
    cout << ans;
    return 0;
}

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