#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define debug(...) cout << "Line: " << __LINE__ << endl; \
prllDebug(", "#__VA_ARGS__, __VA_ARGS__)
template <typename T>
void prllDebug(const char* name, T&& arg1) { cout << (name + 2) << " = " << arg1 << endl; }
template <typename T, typename... T2>
void prllDebug(const char* names, T&& arg1, T2&&... args) {
const char* end = strchr(names + 1, ',');
cout.write(names + 2, end - names - 2) << " = " << arg1 << endl;
prllDebug(end, args...);
}
const ll MAX_N = 6e5 + 10;
ll a[MAX_N], b[MAX_N];
ll n;
ll k;
ll t[MAX_N];
ll tree[4 * MAX_N];
ll treeUnder[MAX_N];
ll treeSum[4 * MAX_N];
void build(ll curr, ll l, ll r) {
if(l == r) {
tree[curr] = treeUnder[l];
return;
}
ll m = (l + r) / 2ll;
build(curr * 2, l, m);
build(curr * 2 + 1, m + 1, r);
tree[curr] = max(tree[curr * 2], tree[curr * 2 + 1]);
}
ll query(ll curr, ll l, ll r, ll ql, ll qr) {
if(ql <= l && r <= qr) {
return tree[curr];
} else if(l > qr || r < ql) {return -1;}
ll m = (l + r) / 2ll;
return max(query(curr * 2, l, m, ql, qr), query(curr * 2 + 1, m + 1, r, ql, qr));
}
void updSum(ll curr, ll l, ll r, ll ind, ll val) {
if(l == r && l == ind) {
treeSum[curr] += val;
return;
} else if(ind < l || r < ind) {return;}
ll m = (l + r) / 2ll;
updSum(curr * 2, l, m, ind, val);
updSum(curr * 2 + 1, m + 1, r, ind, val);
tree[curr] = tree[curr * 2] + tree[curr * 2 + 1];
}
ll querySum(ll curr, ll l, ll r, ll ql, ll qr) {
if(ql <= l && r <= qr) {
return treeSum[curr];
} else if(l > qr || r < ql) {return 0;}
ll m = (l + r) / 2ll;
return query(curr * 2, l, m, ql, qr) + query(curr * 2 + 1, m + 1, r, ql, qr);
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
fill(treeUnder, treeUnder + MAX_N, -1);
cin >> n >> k;
vector<ll> c;
for(ll i = 0; i < n; i ++) {
cin >> a[i] >> b[i];
c.push_back(a[i]);
c.push_back(b[i]);
}
for(ll i = 0; i < k; i ++) {
cin >> t[i];
c.push_back(t[i]);
}
sort(c.begin(), c.end());
c.resize(unique(c.begin(), c.end()) - c.begin());
for(ll i = 0; i < n; i ++) {
a[i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin();
b[i] = lower_bound(c.begin(), c.end(), b[i]) - c.begin();
}
for(ll i = 0; i < k; i ++) {
t[i] = lower_bound(c.begin(), c.end(), t[i]) - c.begin();
treeUnder[t[i]] = i;
}
build(1, 0, c.size() - 1);
vector<pair<ll, ll> > srt;
vector<pair<ll, ll> > readyTo;
for(ll i = 0; i < n; i ++) {
srt.push_back({max(a[i], b[i]), i});
}
for(ll i = 0; i < k; i ++) {
readyTo.push_back({t[i], i});
}
sort(srt.rbegin(), srt.rend());
sort(readyTo.rbegin(), readyTo.rend());
ll ptr = 0, ret = 0;
for(ll i = 0; i < n; i ++) {
ll ind = srt[i].second;
while(ptr < k && srt[i].first <= readyTo[ptr].first) {
updSum(1, 0, MAX_N - 1, readyTo[ptr].second, 1);
ptr ++;
}
if(a[ind] == b[ind]) {
ret += c[a[ind]];
continue;
}
ll mn = min(a[ind], b[ind]), mx = max(a[ind], b[ind]);
ll l = query(1, 0, MAX_N - 1, mn, mx - 1);
ll cnt = querySum(1, 0, MAX_N - 1, l + 1, MAX_N - 1);
if(a[ind] < b[ind]) {
if(cnt & 1) {
ret += c[a[ind]];
} else {
ret += c[b[ind]];
}
} else {
if(cnt & 1) {
ret += c[b[ind]];
} else {
ret += c[a[ind]];
}
}
}
cout << ret << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
