#include <iostream>
#include <algorithm>
using namespace std;
#define BU 450
pair<pair<int,int>,bool> p[200005];
int lim[200005],lazy[800005];
bool cmp(pair<pair<int,int>,bool> a,pair<pair<int,int>,bool> b)
{
return (a.first.second<b.first.second);
}
int merge(int x,int y)
{
if (!y)
return x;
if (!x)
return y;
if (y==-1)
return 3-x;
return y;
}
void update(int node,int st,int en,int l,int r,int f)
{
if (st!=en)
{
lazy[2*node]=merge(lazy[2*node],lazy[node]);
lazy[2*node+1]=merge(lazy[2*node+1],lazy[node]);
lazy[node]=0;
}
if (en<l || st>r || r<l)
return;
if (l<=st && en<=r)
{
lazy[node]=merge(lazy[node],f);
return;
}
int mid=(st+en)/2;
update(2*node,st,mid,l,r,f);
update(2*node+1,mid+1,en,l,r,f);
}
long long query(int node,int st,int en,int idx)
{
if (st!=en)
{
lazy[2*node]=merge(lazy[2*node],lazy[node]);
lazy[2*node+1]=merge(lazy[2*node+1],lazy[node]);
lazy[node]=0;
}
if (st==en)
return lazy[node];
else
{
int mid=(st+en)/2;
if (st<=idx && idx<=mid)
return query(2*node,st,mid,idx);
return query(2*node+1,mid+1,en,idx);
}
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for (int i=0;i<n;i++)
{
scanf("%d%d",&p[i].first.first,&p[i].first.second);
if (p[i].first.first>p[i].first.second)
{
swap(p[i].first.first,p[i].first.second);
p[i].second=1;
}
}
sort(p,p+n);
for (int i=0;i<n;i+=BU)
lim[i]=p[min(i+BU,n)-1].first.first;
for (int i=0;i<n;i+=BU)
sort(p+i,p+i+min(BU,n-i),cmp);
for (int i=0;i<n;i++)
update(1,0,n-1,i,i,(int)p[i].second+1);
while (k--)
{
int x;
scanf("%d",&x);
for (int i=0;i<n;i+=BU)
{
if (lim[i]>x)
{
for (int j=i;j<min(i+BU,n);j++)
{
int tmp=query(1,0,n-1,j);
if ((tmp==1 && p[j].first.first<=x) || (tmp==2 && p[j].first.second<=x))
update(1,0,n-1,j,j,-1);
}
break;
}
int st=i-1,en=min(i+BU,n)-1;
while (st!=en)
{
int mid=(st+en+1)/2;
if (p[mid].second<=x)
st=mid;
else
en=mid-1;
}
update(1,0,n-1,i,st,-1);
update(1,0,n-1,st+1,min(i+BU,n)-1,2);
}
}
long long ans=0;
for (int i=0;i<n;i++)
{
if (query(1,0,n-1,i)==1)
ans+=p[i].first.first;
else
ans+=p[i].first.second;
}
printf("%lld",ans);
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&k);
~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&p[i].first.first,&p[i].first.second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
