#include <bits/stdc++.h>
#define DIM 200010
using namespace std;
struct card{
int x,y,poz;
} v[DIM];
int aint[DIM*4],aib[DIM],poz[DIM],w[DIM*3],swapped[DIM],sol[DIM];
vector <pair<int,int> > events;
pair <int,int> t[DIM];
int n,i,j,k,el;
int cautare_binara (int v[], int n, int val){
int st = 1, dr = n;
while (st <= dr){
int mid = (st+dr)>>1;
if (v[mid] == val)
return mid;
if (v[mid] < val)
st = mid+1;
else dr = mid-1;
}
}
void build (int nod, int st, int dr){
if (st == dr){
aint[nod] = t[st].second;
return;
}
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]);
}
int query (int nod, int st, int dr, int x, int y){
if (x <= st && dr <= y)
return aint[nod];
int mid = (st+dr)>>1, sol_st = 0, sol_dr = 0;
if (x <= mid)
sol_st = query (nod<<1,st,mid,x,y);
if (y > mid)
sol_dr = query ((nod<<1)|1,mid+1,dr,x,y);
return max (sol_st,sol_dr);
}
inline int cmp (pair <int,int> a, pair <int,int> b){
return a.second < b.second;
}
inline int cmp2 (card a, card b){
return a.y < b.y;
}
inline int cmp3 (pair <int,int> a, pair <int,int> b){
return a.first > b.first;
}
inline int cmp4 (card a, card b){
return a.poz < b.poz;
}
void update_aib (int p, int val){
for (;p<=n;p+=(p&-p))
aib[p] += val;
}
int query_aib (int p){
int sol = 0;
for (;p;p-=(p&-p))
sol += aib[p];
return sol;
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>k;
for (i=1;i<=n;i++){
cin>>v[i].x>>v[i].y;
if (v[i].x > v[i].y){
swap (v[i].x,v[i].y);
swapped[i] = 1;
}
v[i].poz = i;
w[++el] = v[i].x;
w[++el] = v[i].y;
}
for (i=1;i<=k;i++){
cin>>t[i].first;
w[++el] = t[i].first;
t[i].second = i;
}
sort (w+1,w+el+1);
int el2 = 1;
for (i=2;i<=el;i++)
if (w[i] != w[i-1])
w[++el2] = w[i];
el = el2;
/*
for (i=1;i<=n;i++){
v[i].x = cautare_binara (w,el,v[i].x);
v[i].y = cautare_binara (w,el,v[i].y);
}
for (i=1;i<=k;i++)
t[i].first = cautare_binara (w,el,t[i].first);
*/
sort (t+1,t+k+1);
build (1,1,k);
for (i=1;i<=n;i++){
int st = 1, dr = k, sol_x = 0, sol_y = 0;
while (st <= dr){
int mid = (st+dr)>>1;
if (t[mid].first >= v[i].x){
sol_x = mid;
dr = mid-1;
} else st = mid+1;
}
st = 1, dr = k;
while (st <= dr){
int mid = (st+dr)>>1;
if (t[mid].first < v[i].y){
sol_y = mid;
st = mid+1;
} else dr = mid-1;
}
if (sol_x && sol_y)
poz[i] = query (1,1,k,sol_x,sol_y);
}
sort (t+1,t+k+1,cmp);
sort (v+1,v+n+1,cmp2);
for (i=1;i<=n;i++)
events.push_back(make_pair(poz[v[i].poz],i));
sort (events.begin(),events.end(),cmp3);
int idx = 0;
for (i=k;i>=0;i--){
int val = t[i].first;
int st = 1, dr = n, sol_poz = 0;
while (st <= dr){
int mid = (st+dr)>>1;
if (v[mid].y <= val){
st = mid+1;
sol_poz = mid;
} else dr = mid-1;
}
if (sol_poz){
update_aib (1,1);
update_aib (sol_poz+1,-1);
}
while (idx < events.size() && events[idx].first == t[i].second){
sol[v[events[idx].second].poz] = query_aib (events[idx].second);
idx++;
}
}
sort (v+1,v+n+1,cmp4);
long long ans = 0;
for (i=1;i<=n;i++){
if (swapped[i])
sol[i]++;
if (sol[i] % 2)
ans += v[i].y;
else ans += v[i].x;
}
cout<<ans;
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:179:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | while (idx < events.size() && events[idx].first == t[i].second){
| ~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int cautare_binara(int*, int, int)':
fortune_telling2.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
25 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
