Submission #466498

#	Time	Username	Problem	Language	Result	Execution time	Memory
466498		stefantaga	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	1398 ms	81796 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;
long long n,m,i,nr[600005],st,dr,sol,mij,solfin[600005],ceau[600005],arb[2400005];
struct wow
{
    long long x,y;
} v[600005];
map <int,int> m2;
pair <int,int> sal[600005];
void update (long long st,long long dr,long long nod,long long poz,long long val)
{
    if (st==dr)
    {
        arb[nod]=val;
        return;
    }
    long long mij=(st+dr)/2;
    if (poz<=mij)
    {
        update(st,mij,2*nod,poz,val);
    }
    else
    {
        update(mij+1,dr,2*nod+1,poz,val);
    }
    arb[nod]=max(arb[2*nod],arb[2*nod+1]);
}
long long query(long long st,long long dr,long long nod,long long ua,long long ub)
{
    if (ua<=st&&dr<=ub)
    {
        return arb[nod];
    }
    long long r1=0,r2=0,mij=(st+dr)/2;
    if (ua<=mij)
    {
        r1=query(st,mij,2*nod,ua,ub);
    }
    if (mij<ub)
    {
        r2=query(mij+1,dr,2*nod+1,ua,ub);
    }
    return max(r1,r2);
}
long long ub(long long x)
{
    return x&(-x);
}
long long aib[400005],nr2;
void upd(long long x,long long val)
{
    long long i;
    for (i=x; i<=nr2; i+=ub(i))
    {
        aib[i]+=val;
    }
}
long long suma(long long poz)
{
    long long i,sumi=0;
    for (i=poz; i>=1; i-=ub(i))
    {
        sumi=sumi+aib[i];
    }
    return sumi;
}
long long inv[600005];
vector <int> ev[600005];
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
#ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
#endif // HOME
    cin>>n>>m;
    for (i=1; i<=n; i++)
    {
        cin>>v[i].x>>v[i].y;
        m2[v[i].x]=1;
        m2[v[i].y]=1;
    }
    for (i=1; i<=m; i++)
    {
        cin>>nr[i];
        m2[nr[i]]=1;
    }
    nr2=0;
    for (auto ind: m2)
    {
        nr2++;
        inv[nr2]=ind.first;
        m2[ind.first]=nr2;
    }
    for (i=1; i<=n; i++)
    {
        v[i].x=m2[v[i].x];
        v[i].y=m2[v[i].y];
    }
    for (i=1; i<=m; i++)
    {
        nr[i]=m2[nr[i]];
    }
    for (i=1; i<=m; i++)
    {
        update(1,nr2,1,nr[i],i);
    }
    for (i=1; i<=n; i++)
    {
        st=min(v[i].x,v[i].y);
        dr=max(v[i].x,v[i].y);
        if (st<dr)
        {
            ceau[i]=query(1,nr2,1,st,dr-1);
        }
    }
    for (i=1; i<=4*nr2; i++)
    {
        arb[i]=0;
    }
    for (i=1; i<=n; i++)
    {
        ev[ceau[i]].push_back(i);
    }
    long long sum=0;
    for (i=m; i>=1; i--)
    {
        for (long long j=0; j<ev[i].size(); j++)
        {
            long long nod=ev[i][j];
            long long dr=max(v[nod].x,v[nod].y);
            long long valu=suma(nr2)-suma(dr-1);
            if (valu%2==0)
            {
                sum=sum+max(inv[v[nod].x],inv[v[nod].y]);
            }
            else
            {
                sum=sum+min(inv[v[nod].x],inv[v[nod].y]);
            }
        }
        if (i!=0)
        {
            upd(nr[i],1);
        }
    }
    for (long long j=0; j<ev[0].size(); j++)
    {
        long long nod=ev[0][j];
        long long dr=max(v[nod].x,v[nod].y);
        long long valu=suma(nr2)-suma(dr-1);
        if (v[nod].x==min(v[nod].x,v[nod].y))
        {
            if (valu%2==1)
            {
                sum=sum+max(inv[v[nod].x],inv[v[nod].y]);
            }
            else
            {
                sum=sum+min(inv[v[nod].x],inv[v[nod].y]);
            }
        }
        else
        {
            if (valu%2==0)
            {
                sum=sum+max(inv[v[nod].x],inv[v[nod].y]);
            }
            else
            {
                sum=sum+min(inv[v[nod].x],inv[v[nod].y]);
            }
        }
    }
    cout<<sum;
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:130:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for (long long j=0; j<ev[i].size(); j++)
      |                             ~^~~~~~~~~~~~~
fortune_telling2.cpp:149:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for (long long j=0; j<ev[0].size(); j++)
      |                         ~^~~~~~~~~~~~~

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