제출 #1247015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247015		sofija6	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	1843 ms	137980 KiB

fortune_telling2

#include <bits/stdc++.h>
#define ll long long
#define MAXN 200010
using namespace std;
ll a[MAXN],b[MAXN],t[MAXN],sz,ans[MAXN],cur=1;
map<ll,ll> val,rval;
struct seg_tree
{
    vector<ll> st;
    void Init()
    {
        sz=1;
        while (sz<cur)
            sz <<= 1;
        st.resize(2*sz+2);
    }
    void Update(ll pos,ll val,ll x,ll lx,ll rx)
    {
        if (lx==rx)
        {
            st[x]=max(st[x],val);
            return;
        }
        ll mid=(lx+rx)/2;
        if (pos<=mid)
            Update(pos,val,2*x,lx,mid);
        else
            Update(pos,val,2*x+1,mid+1,rx);
        st[x]=max(st[2*x],st[2*x+1]);
    }
    ll Calc(ll l,ll r,ll x,ll lx,ll rx)
    {
        if (lx>r || rx<l)
            return 0;
        if (lx>=l && rx<=r)
            return st[x];
        ll mid=(lx+rx)/2;
        return max(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
    }
};
seg_tree S;
struct bit
{
    vector<ll> v;
    void Init()
    {
        v.resize(cur+10);
    }
    void Add(ll pos,ll val)
    {
        for (ll i=pos;i<=cur;i+=i&(-i))
            v[i]+=val;
    }
    ll Calc(ll pos)
    {
        ll ans=0;
        for (ll i=pos;i>0;i-=i&(-i))
            ans+=v[i];
        return ans;
    }
    ll Sum(ll l,ll r)
    {
        return Calc(r)-Calc(l-1);
    }
};
bit B;
vector<ll> ind[MAXN];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,k;
    set<ll> s;
    cin >> n >> k;
    for (ll i=1;i<=n;i++)
    {
        cin >> a[i] >> b[i];
        s.insert(a[i]);
        s.insert(b[i]);
    }
    for (ll i=1;i<=k;i++)
    {
        cin >> t[i];
        s.insert(t[i]);
    }
    for (ll i : s)
    {
        rval[cur]=i;
        val[i]=cur++;
    }
    for (ll i=1;i<=n;i++)
    {
        a[i]=val[a[i]];
        b[i]=val[b[i]];
    }
    S.Init();
    for (ll i=1;i<=k;i++)
    {
        t[i]=val[t[i]];
        S.Update(t[i],i,1,1,sz);
    }
    for (ll i=1;i<=n;i++)
    {
        if (a[i]==b[i])
            continue;
        ll x=S.Calc(min(a[i],b[i]),max(a[i],b[i])-1,1,1,sz);
        ind[x].push_back(i);
    }
    B.Init();
    for (ll i=k;i>0;i--)
    {
        B.Add(t[i],1);
        for (ll j : ind[i])
        {
            ll x=B.Sum(max(a[j],b[j]),cur);
            if (x&1)
                ans[j]=min(a[j],b[j]);
            else
                ans[j]=max(a[j],b[j]);
        }
    }
    for (ll i=1;i<=n;i++)
    {
        if (!ans[i])
        {
            ll x=B.Sum(max(a[i],b[i]),cur);
            if (x&1)
                ans[i]=b[i];
            else
                ans[i]=a[i];
        }
    }
    ll sum=0;
    for (ll i=1;i<=n;i++)
        sum+=rval[ans[i]];
    cout << sum;
    return 0;
}

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