#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
#define bit(x,y) ((x >> y) & 1)
const ll N = 2e5 + 5;
const ll inf = LLONG_MAX/4;
pair<ll,ll> t[N];
ll a[N],b[N],sus[20][N],haha[N];
ll siu[N],id[N];
vector<ll> messi[N];
ll maxr(ll l, ll r)
{
ll sz = (r - l + 1);
ll tmp = 1;
ll cnt = 0;
while(tmp * 2 <= sz)
{
tmp *= 2;
cnt++;
}
return max(sus[cnt][l],sus[cnt][r - tmp + 1]);
}
struct segtree
{
ll n;
ll b[N * 4];
void build(ll n)
{
this->n = n;
}
void udt(ll x)
{
b[x]++;
}
ll get(ll l, ll r)
{
ll ans = 0;
ll i,j;
for(i = l;i <= r;i++) ans += b[i];
return ans;
}
};
segtree f;
int main()
{
ll n,q;
cin >> n >> q;
f.build(q);
ll i,j;
set<ll> tmp;
for(i = 1;i <= n;i++)
{
cin >> a[i] >> b[i];
}
for(i = 1;i <= q;i++)
{
cin >> t[i].first;
t[i].second = i;
}
sort(t + 1,t + 1 + q);
for(i = 1;i <= q;i++)
{
id[t[i].second] = i;
sus[0][i] = t[i].second;
}
for(i = 1;i < 20;i++)
{
for(j = 1;j <= q;j++)
{
sus[i][j] = max(sus[i - 1][j],sus[i - 1][j + (1 << (i - 1))]);
}
}
for(i = 1;i <= n;i++)
{
ll s = min(a[i],b[i]);
ll e = max(a[i],b[i]) - 1;
if(s > t[q].first || t[1].first > e) continue;
ll l = 1,r = q;
ll k1,k2;
while(true)
{
if(l == r)
{
k1 = l;
break;
}
if(l + 1 == r)
{
if(t[l].first >= s) k1 = l;
else k1 = r;
break;
}
ll mid = (l + r) / 2;
if(t[mid].first >= s) r = mid;
else l = mid + 1;
}
l = 1;
r = q;
while(true)
{
if(l == r)
{
k2 = l;
break;
}
if(l + 1 == r)
{
if(t[r].first <= e) k2 = r;
else k2 = l;
break;
}
ll mid = (l + r) / 2;
if(t[mid].first <= e) l = mid;
else r = mid - 1;
}
if(k1 > k2) haha[i] = 0;
else haha[i] = maxr(k1,k2);
}
for(i = 1;i <= n;i++)
{
messi[haha[i]].push_back(i);
//cout << haha[i] << " ";
}
for(i = q;i >= 0;i--)
{
for(auto x : messi[i])
{
if(i > 0)
{
if(a[x] > b[x])
{
swap(a[x],b[x]);
siu[x] = 1;
}
}
ll e = max(a[x],b[x]) - 1;
ll l = 1,r = q + 1;
ll k;
while(true)
{
if(l == r)
{
k = l;
break;
}
if(l + 1 == r)
{
if(e <= t[l].first) k = l;
else k = r;
break;
}
ll mid = (l + r)/ 2;
if(e <= t[mid].first) r = mid;
else l = mid + 1;
}
if(r == q + 1) continue;
siu[x] += f.get(k,q);
}
if(i > 0) f.udt(id[i]);
}
ll ans = 0;
for(i = 1;i <= n;i++)
{
if(siu[i] % 2 == 0) ans += a[i];
else ans += b[i];
}
cout << ans;
}
Compilation message
fortune_telling2.cpp: In member function 'long long int segtree::get(long long int, long long int)':
fortune_telling2.cpp:39:14: warning: unused variable 'j' [-Wunused-variable]
39 | ll i,j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
41296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
41296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
41296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
