#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <map>
#include <vector>
#include <set>
using namespace std;
int x[200005],y[200005];
pair < int , int > all[200005];
vector < pair < pair < int , int > , pair < int , int > > > a,b;
bool F(pair < int , int > a,pair < int , int > b)
{
if(a.first>b.first) return 1;
if(a.first<b.first) return 0;
return a.second<b.second;
}
set < int > vis;
struct A
{
int l,r;
int nxl,nxr,nxt;
int add;
vector < pair < pair < int ,int > , int > > all;
}Node[40005*35+5];
struct B
{
int l,r;
int nxl,nxr;
int con;
}Node2[1000005];
int now=1;
void New(int l,int r,int a,int here)
{
Node[here].l=l;
Node[here].r=r;
Node[here].add=0;
Node[here].nxl=-1;
Node[here].nxr=-1;
Node[here].nxt=a;
}
int Find(int x,int y,int here)
{
int t=0;
if(here==-1) return 0;
if(upper_bound(Node[here].all.begin(),Node[here].all.end(),make_pair(make_pair(y+1,(int) -1),(int) -1))==Node[here].all.begin()) t=0;
else
{
auto a=*prev(upper_bound(Node[here].all.begin(),Node[here].all.end(),make_pair(make_pair(y+1,(int) -1),(int) -1)));
if(a.first.first<=y&&a.first.second>=y) t+=a.second;
}
if(Node[here].l==Node[here].r) return t;
if(x<=(Node[here].l+Node[here].r)/2) t+=Find(x,y,Node[here].nxl);
else t+=Find(x,y,Node[here].nxr);
return t;
}
void add(int l1,int r1,int l2,int r2,int con,int here)
{
int t;
if(l1==Node[here].l&&r1==Node[here].r)
{
Node[here].all.push_back(make_pair(make_pair(l2,r2),con));
return;
}
if(r1<=(Node[here].l+Node[here].r)/2)
{
if(Node[here].nxl==-1)
{
Node[here].nxl=now++;
New(Node[here].l,(Node[here].l+Node[here].r)/2,-1,Node[here].nxl);
}
add(l1,r1,l2,r2,con,Node[here].nxl);
}
else if(l1>(Node[here].l+Node[here].r)/2)
{
if(Node[here].nxr==-1)
{
Node[here].nxr=now++;
New((Node[here].l+Node[here].r)/2+1,Node[here].r,-1,Node[here].nxr);
}
add(l1,r1,l2,r2,con,Node[here].nxr);
}
else
{
if(Node[here].nxl==-1)
{
Node[here].nxl=now++;
New(Node[here].l,(Node[here].l+Node[here].r)/2,-1,Node[here].nxl);
}
add(l1,(Node[here].l+Node[here].r)/2,l2,r2,con,Node[here].nxl);
if(Node[here].nxr==-1)
{
Node[here].nxr=now++;
New((Node[here].l+Node[here].r)/2+1,Node[here].r,-1,Node[here].nxr);
}
add((Node[here].l+Node[here].r)/2+1,r1,l2,r2,con,Node[here].nxr);
}
}
void BFS(int here)
{
if(here==-1) return ;
sort(Node[here].all.begin(),Node[here].all.end());
BFS(Node[here].nxl);
BFS(Node[here].nxr);
}
int main()
{
int N,K,i,j,con,ok=0,ans=0,con2=0,tt,tt2;
scanf("%d %d",&N,&K);
for(i=0;i<N;i++) scanf("%d %d",&x[i],&y[i]);
for(i=1;i<=K;i++)
{
scanf("%d",&all[i].first);
all[i].second=i;
}
vis.insert(0);
vis.insert(1e9+5);
for(i=K;i>=1;i--)
{
con=0;
for(j=i+1;j<=K;j++) if(all[j].first>all[i].first) con++;
if(vis.find(all[i].first)!=vis.end()) continue;
tt=*vis.upper_bound(all[i].first);
tt2=*prev(vis.upper_bound(all[i].first));
if(con%2==0)
{
a.push_back(make_pair(make_pair(all[i].first+1,tt),make_pair(tt2+1,all[i].first)));
b.push_back(make_pair(make_pair(tt2+1,all[i].first),make_pair(all[i].first+1,tt)));
}
else
{
b.push_back(make_pair(make_pair(all[i].first+1,tt),make_pair(tt2+1,all[i].first)));
a.push_back(make_pair(make_pair(tt2+1,all[i].first),make_pair(all[i].first+1,tt)));
}
vis.insert(all[i].first);
}
New(0,1e9+5,-1,0);
all[0].first=1e9+5;
all[0].second=0;
sort(all+1,all+K+1,F);
all[K+1].first=0;
all[K+1].second=K+1;
for(i=1;i<=K+1;i++)
{
con=0;
con2=i;
if(all[i].first!=all[i-1].first)
{
if(con2%2==1) a.push_back(make_pair(make_pair(all[i].first+1,all[i-1].first),make_pair(all[i].first+1,all[i-1].first)));
else b.push_back(make_pair(make_pair(all[i].first+1,all[i-1].first),make_pair(all[i].first+1,all[i-1].first)));
}
}
for(auto j:a) add(j.first.first,j.first.second,j.second.first,j.second.second,1,0);
for(auto j:b) add(j.first.first,j.first.second,j.second.first,j.second.second,1e9,0);
BFS(0);
for(i=0;i<N;i++)
{
ok=0;
ok=Find(x[i],y[i],0);
if(ok==1000000000) ans+=y[i];
else if(ok==1) ans+=x[i];
else while(1);
}
printf("%d\n",ans);
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'void add(int, int, int, int, int, int)':
fortune_telling2.cpp:65:9: warning: unused variable 't' [-Wunused-variable]
65 | int t;
| ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
117 | scanf("%d %d",&N,&K);
| ~~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:118:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
118 | for(i=0;i<N;i++) scanf("%d %d",&x[i],&y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
121 | scanf("%d",&all[i].first);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
67308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
67308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
67308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
