Submission #1100912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100912		vjudge1	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	210 ms	55860 KiB

fortune_telling2

#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
#define bit(x,y) ((x >> y) & 1)
const ll N = 2e5 + 5;
const ll inf = LLONG_MAX/4;
pair<ll,ll> t[N];
ll a[N],b[N],sus[20][N],haha[N];
ll siu[N],id[N];
vector<ll> messi[N];
ll maxr(ll l, ll r)
{
    int p = __lg(r - l + 1);
    return max(sus[p][l],sus[p][r - (1 << p) + 1]);
}
struct segtree
{
    ll n;
    ll b[N * 4];
    void build(ll n)
    {
        this->n = n;
    }
    void udt(ll x)
    {
        udt(0,1,n,x);
    }
    void udt(ll x, ll l, ll r, ll u)
    {
        if(l == r)
        {
            b[x]++;
        }else
        {
            ll mid = (l + r) / 2;
            if(u <= mid) udt(x * 2 + 1,l,mid,u);
            else udt(x * 2 + 2,mid + 1,r,u);
            b[x] = b[x * 2 + 1] + b[x * 2 + 2];
        }
    }
    ll get(ll l, ll r)
    {
        return get(0,1,n,l,r);
    }
    ll get(ll x, ll l, ll r, ll s, ll e)
    {
        if(e < l || r < s) return 0;
        if(s <= l && r <= e) return b[x];
        ll mid = (l + r) / 2;
        return get(x * 2 + 1,l,mid,s,e) + get(x * 2 + 2,mid + 1,r,s,e);
    }
};
segtree f;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n,q;
    cin >> n >> q;
    f.build(q);
    ll i,j;
    set<ll> tmp;
    for(i = 1;i <= n;i++)
    {
        cin >> a[i] >> b[i];
    }
    for(i = 1;i <= q;i++)
    {
        cin >> t[i].first;
        t[i].second = i;
    }
    sort(t + 1,t + 1 + q);
    for(i = 1;i <= q;i++)
    {
        id[t[i].second] = i;
        sus[0][i] = t[i].second;
    }
    for(i = 1;i < 20;i++)
    {
        for(j = 1;j <= q;j++)
        {
            sus[i][j] = max(sus[i - 1][j],sus[i - 1][j + (1 << (i - 1))]);
        }
    }
    for(i = 1;i <= n;i++)
    {
        ll s = min(a[i],b[i]);
        ll e = max(a[i],b[i]) - 1;
        if(s > t[q].first || t[1].first > e) continue;
        ll l = 1,r = q;
        ll k1,k2;
        while(true)
        {
            if(l == r)
            {
                k1 = l;
                break;
            }
            if(l + 1 == r)
            {
                if(t[l].first >= s) k1 = l;
                else k1 = r;
                break;
            }
            ll mid = (l + r) / 2;
            if(t[mid].first >= s) r = mid;
            else l = mid + 1;
        }
        l = 1;
        r = q;
        while(true)
        {
            if(l == r)
            {
                k2 = l;
                break;
            }
            if(l + 1 == r)
            {
                if(t[r].first <= e) k2 = r;
                else k2 = l;
                break;
            }
            ll mid = (l + r) / 2;
            if(t[mid].first <= e) l = mid;
            else r = mid - 1;
        }
        if(k1 > k2) haha[i] = 0;
        else haha[i] = maxr(k1,k2);
    }
    for(i = 1;i <= n;i++)
    {
        messi[haha[i]].push_back(i);
    }
    for(i = q;i >= 0;i--)
    {
        for(auto x : messi[i])
        {
            if(i > 0)
            {
                if(a[x] < b[x])
                {
                    siu[x] = 1;
                }
            }

            ll e = max(a[x],b[x]);
            ll l = 1,r = q + 1;
            ll k;
            while(true)
            {
                if(l == r)
                {
                    k = l;
                    break;
                }
                if(l + 1 == r)
                {
                    if(e <= t[l].first) k = l;
                    else k = r;
                    break;
                }
                ll mid = (l + r)/ 2;
                if(e <= t[mid].first) r = mid;
                else l = mid + 1;
            }
            if(k == q + 1) continue;
            siu[x] += f.get(k,q);
        }
        if(i > 0) f.udt(id[i]);
    }
    ll ans = 0;
    for(i = 1;i <= n;i++)
    {
        if(siu[i] % 2 == 0)
        {
            ans += a[i];
        }else
        {
            ans += b[i];
        }
    }
    cout << ans;
}

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