Submission #465910

#	Time	Username	Problem	Language	Result	Execution time	Memory
465910		stefantaga	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	4 ms	5040 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;
int n,m,i,nr[200005],st,dr,sol,mij,solfin[200005],ceau[200005],arb[800005];
struct wow
{
    int x,y;
}v[200005];
map <int,int> m2;
pair <int,int> sal[200005];
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 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;
    }
    int 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>=0;i--)
    {
        for (int j=0;j<ev[i].size();j++)
        {
            int nod=ev[i][j],valu=query(1,nr2,1,v[nod].y,nr2);
            if (valu==0)
            {
                sum=sum+inv[v[nod].x];
            }
            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]);
            }
        }
        if (i!=0)
        {
               update(1,nr2,1,nr[i],1);
        }
    }
    cout<<sum;
    return 0;
}

Compilation message (stderr)

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

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