/*Code by TMQ*/
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define task "1"
#define ii pair<ll, ll >
#define fi first
#define se second
#define pb push_back
#define em emplace
#define all(x) (x).begin(), (x).end()
#define sall(x) sort(all(x))
#define rall(x) reverse(all(x))
#define reset(a, x) (memset(a, x, sizeof(a)));
#define testcase ll tc; cin >> tc; while(tc--) solve();
ll inline gcd(ll a, ll b) { return !b ? abs(a) : gcd(b, a % b); }
ll inline lcm(ll a, ll b) { return (a / gcd(a, b) * b); }
///============================================================================
#define BIT(i,mask) ((mask >> (i-1)) & 1)
#define DAOBIT(i,mask) ((mask ^ (1<<i-1)))
#define OFFBIT(i,mask) ((mask & ~(1 << (i - 1))))
#define ONBIT(i,mask) ((mask | (1 << (i - 1))))
///============================================================================
const ll mod = 1000000007;
const ll mod1 = 998244353;
const ll inf = 1000000000000000000 + 10;
const ll nmax = 200002;
///============================================================================
using namespace std;
///============================================================================
ll a[nmax][2], query[nmax];
ll n, k;
ll res;
vector<ll> t[nmax * 4];
vector<ll> operator +(vector<ll>& a, vector<ll>& b)
{
vector<ll> ans;
ll i, j;
i = j = 0;
while (i < a.size() && j < b.size())
{
if (a[i] < b[j])
ans.pb(a[i++]);
else ans.pb(b[j++]);
}
for (; i < a.size(); ++i)
ans.pb(a[i]);
for (; j < b.size(); ++j)
ans.pb(b[j]);
return ans;
}
void build(ll l, ll r, ll k = 1)
{
if (l == r)
{
t[k].pb(query[l]);
return;
}
ll mid = (l + r) >> 1;
build(l, mid, k << 1);
build(mid + 1, r, k << 1 | 1);
t[k] = t[k << 1] + t[k << 1 | 1];
}
ii get(ll l, ll r, ll x, ll y, ll k = 1)
{
auto it = lower_bound(all(t[k]), x);
if (it == t[k].end())
return{ 0, 0 };
if (*it >= y)
return { 0, t[k].end() - it };
ll mid = (l + r) >> 1;
if (l == r)
{
///if (*it >= x && *it <= y)
return { 1, 0 };
}
ii get2 = get(mid + 1, r, x, y, k * 2 + 1);
if (get2.fi)
return get2;
ii get1 = get(l, mid, x, y, k * 2);
return { get1.fi, get1.se + get2.se };
}
///============================================================================
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
///freopen(task".inp", "r", stdin);
///freopen(task".outt", "w", stdout);
cin >> n >> k;
for (ll i = 1; i <= n; i++)
cin >> a[i][0] >> a[i][1];
for (ll i = 1; i <= k; i++)
cin >> query[i];
build(1, k);
// for (auto x : t[1])
// cout << x << ' ';
for (ll i = 1; i <= n; i++)
{
ii ans = get(1, n, min(a[i][0], a[i][1]), max(a[i][0], a[i][1]));
///cerr << ans.fi << ' ' << ans.se << '\n';
if (ans.fi > 0 && a[i][0] < a[i][1])
swap(a[i][0], a[i][1]);
res += a[i][ans.se & 1];
}
cout << res;
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'std::vector<long long int> operator+(std::vector<long long int>&, std::vector<long long int>&)':
fortune_telling2.cpp:41:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | while (i < a.size() && j < b.size())
| ~~^~~~~~~~~~
fortune_telling2.cpp:41:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | while (i < a.size() && j < b.size())
| ~~^~~~~~~~~~
fortune_telling2.cpp:47:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (; i < a.size(); ++i)
| ~~^~~~~~~~~~
fortune_telling2.cpp:49:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (; j < b.size(); ++j)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
