#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <chrono>
#include <random>
#include <bitset>
#include <utility>
int n, k;
int A[200005], B[200005];
int l[200005], r[200005];
int q[200005];
int BIT[200005];
void Add(int id, int value)
{
for(id; id <= k; id += id & -id)
{
BIT[id] += value;
}
}
int Get(int id)
{
int ans = 0;
for(id; id > 0; id -= id & -id)
{
ans += BIT[id];
}
return ans;
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> n >> k;
for(int i = 1; i <= n; i++)
{
std::cin >> A[i] >> B[i];
l[i] = 0;
r[i] = k;
}
for(int i = 1; i <= k; i++)
{
std::cin >> q[i];
}
for(int turn = 1; turn <= 20; turn++)
{
std::vector <std::vector <int> > Query(k + 1, std::vector <int> ());;
for(int i = 1; i <= n; i++)
{
int mid = (l[i] + r[i] + 1) >> 1;
if(l[i] != r[i])
Query[mid].push_back(i);
}
std::set <int> S;
for(int i = k; i > 0; i--)
{
S.insert(q[i]);
for(auto x : Query[i])
{
auto value = S.lower_bound(std::min(A[x], B[x]));
if(value != S.end() and *value < std::max(A[x], B[x]))
{
l[x] = i;
}
else
{
r[x] = i - 1;
}
}
}
}
long long ans = 0;
std::vector <std::vector <int> > Query(k + 1, std::vector <int> ());
std::vector <int> Q;
for(int i = 1; i <= k; i++)
{
Q.push_back(q[i]);
}
Q.push_back(0);
std::sort(Q.begin(), Q.end());
Q.erase(unique(Q.begin(), Q.end()), Q.end());
for(int i = 1; i <= n; i++)
{
Query[l[i]].push_back(i);
}
for(int i = k; i >= 0; i--)
{
for(auto x : Query[i])
{
bool turn = (i == 0) ? 0 : A[x] > B[x];
int cnt = k - i - Get(lower_bound(Q.begin(), Q.end(), std::max(A[x], B[x])) - Q.begin() - 1);
turn ^= (cnt & 1);
if(turn)
{
ans += B[i];
}
else
{
ans += A[i];
}
}
if(i)
{
Add(lower_bound(Q.begin(), Q.end(), q[i]) - Q.begin(), 1);
}
}
std::cout << ans << '\n';
}
Compilation message
fortune_telling2.cpp: In function 'void Add(int, int)':
fortune_telling2.cpp:25:6: warning: statement has no effect [-Wunused-value]
25 | for(id; id <= k; id += id & -id)
| ^~
fortune_telling2.cpp: In function 'int Get(int)':
fortune_telling2.cpp:34:6: warning: statement has no effect [-Wunused-value]
34 | for(id; id > 0; id -= id & -id)
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
