#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define II pair < int , int >
#define pb push_back
#define mset(a , b) memset(a , b , sizeof a)
#define all(a) (a).begin() , (a).end()
#define Hmax priority_queue < int >
#define Hmin priority_queue < int , vector < int > , greater < int > >
#define IImax priority_queue < II >
#define IImin priority_queue < II , vector < II > , greater < II > >
const int inf = 1e15;
const int N = 2e5 + 5;
int n , k , a[N] , b[N] , c[N] , S[4 * N] , F[N] , Out[N] , Poss[N];
vector < II > List;
vector < int > vc;
void Input()
{
cin >> n >> k;
for(int i = 1 ; i <= n ; ++i)
{
cin >> a[i] >> b[i];
}
for(int i = 1 ; i <= k ; ++i)
{
cin >> c[i];
vc.pb(c[i]);
}
sort(all(vc));
}
void Update(int Id , int Low , int High , int u , int Val)
{
if(High < u || Low > u) return;
if(Low == High)
{
S[Id] = max(S[Id] , Val);
return;
}
int Mid = (Low + High) / 2;
Update(2 * Id , Low , Mid , u , Val);
Update(2 * Id + 1 , Mid + 1 , High , u , Val);
S[Id] = max(S[2 * Id] , S[2 * Id + 1]);
}
int Query(int Id , int Low , int High , int u , int v)
{
if(High < u || Low > v) return 0;
if(u <= Low && High <= v) return S[Id];
int Mid = (Low + High) / 2;
return max(Query(2 * Id , Low , Mid , u , v) , Query(2 * Id + 1 , Mid + 1 , High , u , v));
}
void Up(int Val)
{
Val = lower_bound(all(vc) , Val) - vc.begin() + 1;
for(int i = Val ; i >= 1 ; i -= (i & -i))
{
F[i]++;
}
}
int Get(int Val)
{
Val = lower_bound(all(vc) , Val) - vc.begin() + 1;
int Ans = 0;
for(int i = Val ; i <= k ; i += (i & -i))
{
Ans += F[i];
}
return Ans;
}
void Solve()
{
for(int i = 1 ; i <= k ; ++i)
{
int Pos = lower_bound(all(vc) , c[i]) - vc.begin() + 1;
Update(1 , 1 , k , Pos , i);
}
for(int i = 1 ; i <= n ; ++i)
{
int Min = min(a[i] , b[i]) , Max = max(a[i] , b[i]);
int Low = lower_bound(all(vc) , Min) - vc.begin() + 1;
int High = lower_bound(all(vc) , Max) - vc.begin();
Poss[i] = Query(1 , 1 , k , Low , High);
List.pb({Poss[i] , i});
}
sort(List.rbegin() , List.rend());
int Cur = k;
for(auto i : List)
{
while(Cur >= i.fi)
{
Up(c[Cur]);
Cur--;
}
Out[i.se] = Get(max(a[i.se] , b[i.se]));
}
int Res = 0;
for(int i = 1 ; i <= n ; ++i)
{
if(Poss[i] == 0)
{
if(Out[i] % 2 == 1) Res += max(a[i] , b[i]);
else Res += min(a[i] , b[i]);
}
else
{
if(Out[i] % 2 == 0) Res += max(a[i] , b[i]);
else Res += min(a[i] , b[i]);
}
}
cout << Res;
}
#undef int
int main()
{
if(fopen("trash.inp" , "r"))
freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout);
// else freopen(".inp" , "r" , stdin) , freopen(".out" , "w" , stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Input();
Solve();
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
122 | freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:122:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
122 | freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
