#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair < int, int > PII;
const int NMAX = 2e5 + 5, KMAX = 2e5 + 5;
int N, K;
PII A[NMAX];
int T[KMAX];
int q;
PII V[KMAX], Q[KMAX];
vector < PII > Queries[NMAX];
/// Fenwick Tree:
int AIB[KMAX];
static inline int UB (int X)
{
return (X & (-X));
}
static inline void Update_1 (int pos, int val)
{
for(int i = pos; i <= q; i += UB(i))
AIB[i] += val;
return;
}
static inline int Query_1 (int pos)
{
int r = 0;
for(int i = pos; i >= 1; i -= UB(i))
r += AIB[i];
return r;
}
///
/// Segment Tree:
int AINT[4 * KMAX];
static inline void Update (int Node, int a, int b, int pos, int val)
{
if(a == b)
{
AINT[Node] = val;
return;
}
int Mid = (a + b) >> 1;
if(pos <= Mid)
Update(2 * Node, a, Mid, pos, val);
if(pos > Mid)
Update(2 * Node + 1, Mid + 1, b, pos, val);
AINT[Node] = max(AINT[2 * Node], AINT[2 * Node + 1]);
return;
}
static inline int Query (int Node, int a, int b, int qa, int qb)
{
if(qa <= a && b <= qb)
return AINT[Node];
int Mid = (a + b) >> 1;
int p1 = 0, p2 = 0;
if(qa <= Mid)
p1 = Query(2 * Node, a, Mid, qa, qb);
if(qb > Mid)
p2 = Query(2 * Node + 1, Mid + 1, b, qa, qb);
return max(p1, p2);
}
///
static inline void Read ()
{
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K;
for(int i = 1; i <= N; ++i)
cin >> A[i].first >> A[i].second;
for(int i = 1; i <= K; ++i)
cin >> T[i], V[i] = {T[i], i};
return;
}
auto cmp = [] (PII A, PII B)
{
if(A.first < B.first)
return 1;
if(A.first > B.first)
return 0;
if(A.second > B.second)
return 1;
return 0;
};
static inline void Precalculation ()
{
sort(V + 1, V + K + 1, cmp);
Q[++q] = V[1];
for(int i = 2; i <= K; ++i)
if(V[i].first != V[i - 1].first)
Q[++q] = V[i];
for(int i = 1; i <= q; ++i)
Update(1, 1, q, i, Q[i].second);
return;
}
static inline int CB1 (int X)
{
int Left = 1, Right = q, ans = -1;
while(Left <= Right)
{
int Mid = (Left + Right) >> 1;
if(Q[Mid].first >= X)
{
ans = Mid;
Right = Mid - 1;
}
else
Left = Mid + 1;
}
return ans;
}
static inline int CB2 (int X)
{
int Left = 1, Right = q, ans = -1;
while(Left <= Right)
{
int Mid = (Left + Right) >> 1;
if(Q[Mid].first <= X)
{
ans = Mid;
Left = Mid + 1;
}
else
Right = Mid - 1;
}
return ans;
}
static inline int Lower (int X)
{
int Left = 1, Right = q, ans = -1;
while(Left <= Right)
{
int Mid = (Left + Right) >> 1;
if(Q[Mid].first >= X)
{
ans = Mid;
Right = Mid - 1;
}
else
Left = Mid + 1;
}
return ans;
}
static inline void Solve ()
{
long long ans = 0;
for(int i = 1; i <= N; ++i)
{
int Last_Index = 0;
int Min = min(A[i].first, A[i].second);
int Max = max(A[i].first, A[i].second);
int p1 = CB1(Min);
int p2 = CB2(Max - 1);
if(p1 == -1 || (p1 > 0 && Q[p1].first >= Max))
Last_Index = 0;
else
Last_Index = Query(1, 1, q, p1, p2);
if(Last_Index && A[i].first < A[i].second)
swap(A[i].first, A[i].second);
/*
int counts = 0;
for(int j = Last_Index + 1; j <= K; ++j)
if(T[j] >= Max)
++counts;
if(counts & 1)
swap(A[i].first, A[i].second);
ans += 1LL * A[i].first;
*/
Queries[Last_Index + 1].push_back({Max, i});
}
for(int i = K; i >= 1; --i)
if(!Queries[i].empty())
{
int pos = Lower(T[i]);
Update_1(pos, 1);
for(auto it : Queries[i])
{
int Val = it.first;
int j = it.second;
int Total = Query_1(q);
int B_E = (Val <= Q[q].first) ? (Query_1(CB1(Val) - 1)) : 0;
int counts = Total - B_E;
if(counts & 1)
swap(A[j].first, A[j].second);
ans += 1LL * A[j].first;
}
}
cout << ans << '\n';
return;
}
int main()
{
Read();
Precalculation();
Solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
