This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*Code by TMQ*/
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define task "name"
#define ii pair<int, int >
#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 int 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;
int s[nmax][2];
int a[nmax];
vector<int> t[nmax * 4];
void build(int k, int l, int r) {
if (l == r) {
t[k] = { a[l] };
return;
}
int i1 = 0, i2 = 0, id1 = k << 1, id2 = k << 1 | 1, s1, s2, m = (l + r) >> 1;
build(id1, l, m);
build(id2, m + 1, r);
s1 = t[id1].size();
s2 = t[id2].size();
while (i1 != s1 && i2 != s2)
if (t[id1][i1] > t[id2][i2])
t[k].pb(t[id2][i2++]);
else
t[k].pb(t[id1][i1++]);
while (i1 != s1)
t[k].pb(t[id1][i1++]);
while (i2 != s2)
t[k].pb(t[id2][i2++]);
}
pair<int, int> query(int k, int l, int r, int f, int s) {
///cout << '\n' << '\n';
auto it = lower_bound(all(t[k]), min(f, s));
if (it == t[k].end())
{
////cerr << t[k].end() - it << '\n';
return { 0, 0 };
}
if (*it >= max(f, s))
{
///cerr << t[k].end() - it << '\n';
return { 0, t[k].end() - it };
}
if (l == r)
return { 1, 0 };
int m = (l + r) >> 1;
auto r2 = query(k << 1 | 1, m + 1, r, f, s);
if (r2.fi) return r2;
auto r1 = query(k << 1, l, m, f, s);
return { r1.fi, r1.se ^ r2.se };
}
ll res;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> s[i][0] >> s[i][1];
for (int i = 1; i <= k; i++)
cin >> a[i];
build(1, 1, k);
for (int i = 1; i <= n; i++) {
auto w = query(1, 1, k, s[i][0], s[i][1]);
///cerr << w.fi << ' ' << w.se << '\n';
///cout << '\n';
if (w.fi && s[i][0] < s[i][1])
swap(s[i][0], s[i][1]);
res += s[i][w.se & 1];
}
cout << res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |