Submission #466495

#	Time	Username	Problem	Language	Result	Execution time	Memory
466495		stefantaga	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	374 ms	23560 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;
int n,m,i,nr[400005],st,dr,sol,mij,solfin[200005],ceau[200005],arb[1600005];
struct wow
{
    int x,y;
} v[400005];
map <int,int> m2;
pair <int,int> sal[400005];
void update (int st,int dr,int nod,int poz,int val)
{
    if (st==dr)
    {
        arb[nod]=val;
        return;
    }
    int 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]);
}
int query(int st,int dr,int nod,int ua,int ub)
{
    if (ua<=st&&dr<=ub)
    {
        return arb[nod];
    }
    int 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);
}
int ub(int x)
{
    return x&(-x);
}
int aib[400005],nr2;
void upd(int x,int val)
{
    int i;
    for (i=x; i<=nr2; i+=ub(i))
    {
        aib[i]+=val;
    }
}
int suma(int poz)
{
    int i,sumi=0;
    for (i=poz; i>=1; i-=ub(i))
    {
        sumi=sumi+aib[i];
    }
    return sumi;
}
int inv[200005];
vector <int> ev[200005];
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 (int j=0; j<ev[i].size(); j++)
        {
            int nod=ev[i][j];
            int dr=max(v[nod].x,v[nod].y);
            int 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 (int j=0; j<ev[0].size(); j++)
    {
        int nod=ev[0][j];
        int dr=max(v[nod].x,v[nod].y);
        int 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:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for (int j=0; j<ev[i].size(); j++)
      |                       ~^~~~~~~~~~~~~
fortune_telling2.cpp:149:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for (int j=0; j<ev[0].size(); j++)
      |                   ~^~~~~~~~~~~~~

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