Submission #741527

#	Time	Username	Problem	Language	Result	Execution time	Memory
741527		bgnbvnbv	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	181 ms	21268 KiB

fortune_telling2

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,k;
struct qq
{
    ll a,b;
    bool ok;
    ll id;
    bool operator<(const qq&o)
    {
        return b<o.b;
    }
}x[maxN];
struct vd
{
    ll t,id;
    bool operator<(const vd&o)
    {
        return t<o.t;
    }
}y[maxN];
ll st[4*maxN];
void upd(ll pos,ll val,ll id=1,ll l=1,ll r=k)
{
    if(l==r)
    {
        st[id]=val;
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid)upd(pos,val,id*2,l,mid);
    else upd(pos,val,id*2+1,mid+1,r);
    st[id]=max(st[id*2],st[id*2+1]);
}
ll bs(ll val,ll id=1,ll l=1,ll r=k)
{
    if(st[id]<val) return l-1;
    if(l==r) return l;
    ll mid=l+r>>1;
    ll pos=bs(val,id*2+1,mid+1,r);
    if(pos==mid) return bs(val,id*2,l,mid);
    return pos;
}
ll bit[maxN];
void update(ll i,ll val)
{
    while(i<=k)
    {
        bit[i]+=val;
        i+=(i&(-i));
    }
}
ll get(ll i)
{
    ll ans=0;
    while(i>0)
    {
        ans+=bit[i];
        i-=(i&(-i));
    }
    return ans;
}
void solve()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++)
    {
        cin >> x[i].a >> x[i].b;
        x[i].ok=false;
        if(x[i].a>x[i].b)
        {
            swap(x[i].a,x[i].b);
            x[i].ok=true;
        }
        x[i].id=i;
    }
    for(int i=1;i<=k;i++)
    {
        cin >> y[i].t;
        y[i].id=i;
        upd(i,y[i].t);
    }
    sort(x+1,x+n+1);
    sort(y+1,y+k+1);
    ll j=k;
    ll ans=0;
    for(int i=n;i>=1;i--)
    {
        while(j>0&&y[j].t>=x[i].b)
        {
            update(y[j].id,1);
            upd(y[j].id,-inf);
            j--;
        }
        ll pos=bs(x[i].a);
        ll sum=get(k);
        if(x[i].ok==true) sum++;
        if(pos!=0)
        {
            sum+=get(pos);
            if(x[i].ok==false) sum++;
        }
        sum%=2;
        if(sum==0) ans+=x[i].a;
        else ans+=x[i].b;
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void upd(ll, ll, ll, ll, ll)':
fortune_telling2.cpp:40:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     ll mid=l+r>>1;
      |            ~^~
fortune_telling2.cpp: In function 'll bs(ll, ll, ll, ll)':
fortune_telling2.cpp:49:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     ll mid=l+r>>1;
      |            ~^~

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