#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int n, q;
const int maxn = 2e5 + 5;
int a[maxn][2];
set <int> st[4*maxn];
int quer[maxn];
vector <int> v[4*maxn];
void Build(int l, int r, int pos)
{
if (l==r)
{
st[pos].insert(quer[l]);
v[pos].push_back(quer[l]);
return;
}
int mid = (l+r)/2;
Build (l, mid, pos*2);
Build (mid + 1, r, pos*2 + 1);
set_union(begin(st[pos*2]), end(st[pos* 2]),
begin(st[pos*2 + 1]), end(st[pos* 2 + 1]),
inserter(st[pos], st[pos].begin()));
for (auto x: st[pos])
{
v[pos].push_back(x);
}
}
bool Respond(int pos, int qa, int qb)
{
if (qa>qb)
{
swap(qa, qb);
}
int l = 0;
int r = v[pos].size() - 1;
while (r-l>1)
{
int mid = (l+r)/2;
if (v[pos][mid]>=qa && v[pos][mid]<qb)
return true;
if (v[pos][mid]<qa)
l = mid;
else r = mid;
}
if (v[pos][l]>=qa && v[pos][l]<qb)
return true;
if (v[pos][r]>=qa && v[pos][r]<qb)
return true;
return false;
}
int FindSelectiveLast(int l, int r, int pos, int qa, int qb)
{
if (l==r)
return l;
int mid = (l+r)/2;
if (Respond(pos*2 + 1, qa, qb))
return FindSelectiveLast(mid + 1, r, pos*2 + 1, qa, qb);
else return FindSelectiveLast(l, mid, pos*2, qa, qb);
}
int Count(int pos, int x)
{
//cout<<"\nCounting "<<pos<<" "<<x<<"\n";
int tot = v[pos].size();
// for (auto y : v[pos])
// // cout<<y<< ' ';
// cout<<"\n";
int l = 0;
int r = tot-1;
while (r-l>1)
{
int mid = (l+r)/2;//cout<<mid<<" "<<v[pos][mid]<<" ";
if (v[pos][mid]>=x){
// cout<<" r updated ";
r = mid;
}
else {
//cout<<" l updated ";
l = mid;
}
//cout<<"\n";
}
// cout<<l <<" "<<r<<"\n";
if (v[pos][l]>=x)
return tot - l;
else return tot - r;
}
int Query(int l, int r, int pos, int ql, int x)
{
// cout<<"positioning "<<l<<" "<<r<<" "<<x<<" ";
int mid = (l+r)/2;
if (ql>r){
//cout<<"NOOB RANGE\n";
return 0;
}
if (l>=ql)
{
//cout<<Count(pos, x)<<"\n";
return Count(pos, x);
}
else
{
//cout<<"Went to child\n";
return Query(l, mid, pos*2, ql, x) + Query(mid + 1, r, pos*2 + 1, ql, x);
}
}
void Solve()
{
cin>>n>>q;
for (int i=1; i<=n; i++)
cin>>a[i][0]>>a[i][1];
for (int i=1; i<=q; i++)
{
int x;
cin>>x;
quer[i] = x;
}
Build(1, q, 1);
int sum = 0;
for (int i=1; i<=n; i++)
{
int sel = 0;
if (Respond(1, a[i][0], a[i][1]))
{
sel = FindSelectiveLast(1, q, 1, a[i][0], a[i][1]);
}
sel++;
//cout<<sel<< " ";
// cout<<"Querying\n";
int vals = Query(1, q, 1, sel, max(a[i][0], a[i][1]));
// cout<<"\n"<<sel<<" "<<vals<<" ";
int initial = 0;
if (sel!=1 && a[i][1]>a[i][0])
{
initial = 1;
}
initial = (initial + vals)%2;
sum += a[i][initial];
// cout<<a[i][initial]<<"\n";
}
cout<<sum;
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
57268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
57268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
57268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
