#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <map>
#include <vector>
#include <set>
#include <assert.h>
using namespace std;
int K;
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,have;
vector < int > Cha;
map < pair < int ,int > , int > all2;
pair < pair < vector < pair < pair < int ,int > , int > > , vector < pair < pair < int ,int > , int > > > , vector < pair < int , pair < int , int > > > > query[1000005];
struct B
{
int l,r;
int nxl,nxr;
int con;
}Node2[2000005];
int now=1,now2=1;
int Find(int y,int here)
{
int t=0;
if(here==-1) return 0;
if(all2.upper_bound((make_pair(y+1,(int) -1)))==all2.begin()) t=0;
else
{
auto a=*prev(all2.upper_bound(make_pair(y+1,(int) -1)));
if(a.first.first<=y&&a.first.second>=y) t+=a.second;
}
return t;
}
int Find2(int l,int r,int here)
{
int t=0;
if(here==-1) return 0;
t=0;
if(l==Node2[here].l&&r==Node2[here].r) return Node2[here].con;
if(r<=(Node2[here].l+Node2[here].r)/2) return Find2(l,r,Node2[here].nxl);
else if(l>(Node2[here].l+Node2[here].r)/2) return Find2(l,r,Node2[here].nxr);
else return Find2(l,(Node2[here].l+Node2[here].r)/2,Node2[here].nxl)+Find2((Node2[here].l+Node2[here].r)/2+1,r,Node2[here].nxr);
}
void add2(int where,int here)
{
Node2[here].con++;
if(where==Node2[here].l&&where==Node2[here].r) return;
if(where<=(Node2[here].l+Node2[here].r)/2)
{
add2(where,Node2[here].nxl);
}
else
{
add2(where,Node2[here].nxr);
}
}
int cha(int here)
{
return lower_bound(Cha.begin(),Cha.end(),here)-Cha.begin();
}
void add(int l1,int r1,int l2,int r2,int con,int here)
{
l1=cha(l1);
r1=cha(r1+1);
query[l1].first.first.push_back(make_pair(make_pair(l2,r2),con));
query[r1].first.second.push_back(make_pair(make_pair(l2,r2),con));
}
void build2(int l,int r,int here)
{
Node2[here].l=l;
Node2[here].r=r;
Node2[here].con=0;
if(l==r) return;
Node2[here].nxl=now2++;
Node2[here].nxr=now2++;
build2(l,(l+r)/2,Node2[here].nxl);
build2((l+r)/2+1,r,Node2[here].nxr);
}
int main()
{
//freopen("03-01.in","rt",stdin);
int N,K,i,j,con,ok=0,con2=0,tt,tt2,ttt=0;
long long ans=0;
scanf("%d %d",&N,&K);
build2(0,1e6,0);
for(i=0;i<N;i++)
{
scanf("%d %d",&x[i],&y[i]);
have.insert(x[i]);
}
//printf("aa\n");
for(i=1;i<=K;i++)
{
scanf("%d",&all[i].first);
//if(i%1000==0) printf("%d %d\n",i,K);
all[i].second=i;
have.insert(all[i].first);
have.insert(all[i].first+1);
}
have.insert(0);
have.insert(0+1);
have.insert(1e9+5);
have.insert(1e9+5+1);
//printf("%d\n",have.size());
//assert(have.size()<=1e6);
for(auto i:have) Cha.push_back(i);
for(i=0;i<N;i++) query[cha(x[i])].second.push_back(make_pair(y[i],make_pair(x[i],y[i])));
vis.insert(0);
vis.insert(1e9+5);
for(i=K;i>=1;i--)
{
con=0;
con2=0;
con=Find2(cha(all[i].first+1),cha(1e9+5),0);
//for(j=i+1;j<=K;j++) if(all[j].first>all[i].first) con2++;
if(vis.find(all[i].first)!=vis.end())
{
add2(cha(all[i].first),0);
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);
add2(cha(all[i].first),0);
}
if(N>40000||K>40000) return 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);
for(i=0;i<1000000;i++)
{
//if(i%1000==0) printf("%d\n",i);
for(auto j:query[i].first.second) all2.erase(j.first);
for(auto j:query[i].first.first) all2[j.first]=j.second;
for(auto j:query[i].second)
{
if(Find(j.first,0)==1) ans+=j.second.first;
else ans+=j.second.second;
}
}
printf("%lld\n",ans);
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int Find2(int, int, int)':
fortune_telling2.cpp:50:9: warning: variable 't' set but not used [-Wunused-but-set-variable]
50 | int t=0;
| ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:98:15: warning: unused variable 'j' [-Wunused-variable]
98 | int N,K,i,j,con,ok=0,con2=0,tt,tt2,ttt=0;
| ^
fortune_telling2.cpp:98:21: warning: unused variable 'ok' [-Wunused-variable]
98 | int N,K,i,j,con,ok=0,con2=0,tt,tt2,ttt=0;
| ^~
fortune_telling2.cpp:98:40: warning: unused variable 'ttt' [-Wunused-variable]
98 | int N,K,i,j,con,ok=0,con2=0,tt,tt2,ttt=0;
| ^~~
fortune_telling2.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
100 | scanf("%d %d",&N,&K);
| ~~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
107 | scanf("%d %d",&x[i],&y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
114 | scanf("%d",&all[i].first);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
110316 KB |
Output is correct |
| 2 |
Correct |
87 ms |
110316 KB |
Output is correct |
| 3 |
Correct |
86 ms |
110444 KB |
Output is correct |
| 4 |
Correct |
87 ms |
110316 KB |
Output is correct |
| 5 |
Correct |
87 ms |
110316 KB |
Output is correct |
| 6 |
Correct |
85 ms |
110316 KB |
Output is correct |
| 7 |
Correct |
86 ms |
110316 KB |
Output is correct |
| 8 |
Correct |
85 ms |
110444 KB |
Output is correct |
| 9 |
Correct |
90 ms |
110444 KB |
Output is correct |
| 10 |
Correct |
85 ms |
110188 KB |
Output is correct |
| 11 |
Correct |
85 ms |
110316 KB |
Output is correct |
| 12 |
Correct |
85 ms |
110316 KB |
Output is correct |
| 13 |
Correct |
85 ms |
110340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
110316 KB |
Output is correct |
| 2 |
Correct |
87 ms |
110316 KB |
Output is correct |
| 3 |
Correct |
86 ms |
110444 KB |
Output is correct |
| 4 |
Correct |
87 ms |
110316 KB |
Output is correct |
| 5 |
Correct |
87 ms |
110316 KB |
Output is correct |
| 6 |
Correct |
85 ms |
110316 KB |
Output is correct |
| 7 |
Correct |
86 ms |
110316 KB |
Output is correct |
| 8 |
Correct |
85 ms |
110444 KB |
Output is correct |
| 9 |
Correct |
90 ms |
110444 KB |
Output is correct |
| 10 |
Correct |
85 ms |
110188 KB |
Output is correct |
| 11 |
Correct |
85 ms |
110316 KB |
Output is correct |
| 12 |
Correct |
85 ms |
110316 KB |
Output is correct |
| 13 |
Correct |
85 ms |
110340 KB |
Output is correct |
| 14 |
Correct |
129 ms |
114080 KB |
Output is correct |
| 15 |
Correct |
198 ms |
118240 KB |
Output is correct |
| 16 |
Correct |
253 ms |
122204 KB |
Output is correct |
| 17 |
Correct |
329 ms |
126308 KB |
Output is correct |
| 18 |
Correct |
339 ms |
126308 KB |
Output is correct |
| 19 |
Correct |
341 ms |
126496 KB |
Output is correct |
| 20 |
Correct |
337 ms |
126324 KB |
Output is correct |
| 21 |
Correct |
324 ms |
126456 KB |
Output is correct |
| 22 |
Correct |
262 ms |
121688 KB |
Output is correct |
| 23 |
Correct |
265 ms |
120792 KB |
Output is correct |
| 24 |
Correct |
235 ms |
119636 KB |
Output is correct |
| 25 |
Correct |
269 ms |
123100 KB |
Output is correct |
| 26 |
Correct |
286 ms |
124636 KB |
Output is correct |
| 27 |
Correct |
305 ms |
125024 KB |
Output is correct |
| 28 |
Correct |
300 ms |
125028 KB |
Output is correct |
| 29 |
Correct |
330 ms |
125788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
110316 KB |
Output is correct |
| 2 |
Correct |
87 ms |
110316 KB |
Output is correct |
| 3 |
Correct |
86 ms |
110444 KB |
Output is correct |
| 4 |
Correct |
87 ms |
110316 KB |
Output is correct |
| 5 |
Correct |
87 ms |
110316 KB |
Output is correct |
| 6 |
Correct |
85 ms |
110316 KB |
Output is correct |
| 7 |
Correct |
86 ms |
110316 KB |
Output is correct |
| 8 |
Correct |
85 ms |
110444 KB |
Output is correct |
| 9 |
Correct |
90 ms |
110444 KB |
Output is correct |
| 10 |
Correct |
85 ms |
110188 KB |
Output is correct |
| 11 |
Correct |
85 ms |
110316 KB |
Output is correct |
| 12 |
Correct |
85 ms |
110316 KB |
Output is correct |
| 13 |
Correct |
85 ms |
110340 KB |
Output is correct |
| 14 |
Correct |
129 ms |
114080 KB |
Output is correct |
| 15 |
Correct |
198 ms |
118240 KB |
Output is correct |
| 16 |
Correct |
253 ms |
122204 KB |
Output is correct |
| 17 |
Correct |
329 ms |
126308 KB |
Output is correct |
| 18 |
Correct |
339 ms |
126308 KB |
Output is correct |
| 19 |
Correct |
341 ms |
126496 KB |
Output is correct |
| 20 |
Correct |
337 ms |
126324 KB |
Output is correct |
| 21 |
Correct |
324 ms |
126456 KB |
Output is correct |
| 22 |
Correct |
262 ms |
121688 KB |
Output is correct |
| 23 |
Correct |
265 ms |
120792 KB |
Output is correct |
| 24 |
Correct |
235 ms |
119636 KB |
Output is correct |
| 25 |
Correct |
269 ms |
123100 KB |
Output is correct |
| 26 |
Correct |
286 ms |
124636 KB |
Output is correct |
| 27 |
Correct |
305 ms |
125024 KB |
Output is correct |
| 28 |
Correct |
300 ms |
125028 KB |
Output is correct |
| 29 |
Correct |
330 ms |
125788 KB |
Output is correct |
| 30 |
Incorrect |
910 ms |
148448 KB |
Output isn't correct |
| 31 |
Halted |
0 ms |
0 KB |
- |
