#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 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>=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=query(1,nr2,1,dr,nr2);
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);
}
}
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=query(1,nr2,1,dr,nr2);
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
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++)
| ~^~~~~~~~~~~~~
fortune_telling2.cpp:127:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for (int j=0;j<ev[0].size();j++)
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
