/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
*/
#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left224
#define right right224
#define next next224
#define rank rank224
#define prev prev224
#define y1 y1224
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
const string FILENAME = "input";
const int MAXN = 200228;
const int INF = 1e9;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int n, k;
int a[MAXN], b[MAXN], t[MAXN];
pair<int, int> p[MAXN];
struct rmq
{
vector<int> d;
int ss = 1;
void init(int n) {
while (ss < n) {
ss <<= 1;
}
d.resize(2 * ss);
for (int i = 0; i < 2 * ss; i++) {
d[i] = -INF;
}
}
void upd(int i, int val) {
i += ss - 1;
d[i] = val;
while (i >> 1 > 0) {
i >>= 1;
d[i] = max(d[i * 2], d[i * 2 + 1]);
}
}
int get(int l, int r) {
l += ss - 1;
r += ss - 1;
int res = -INF;
while (l <= r) {
if (l & 1) {
chkmax(res, d[l]);
l++;
}
if (!(r & 1)) {
chkmax(res, d[r]);
r--;
}
l >>= 1;
r >>= 1;
}
return res;
}
};
rmq kek;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//read(FILENAME);
cin >> n >> k;
vector<int> vx;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
vx.pb(a[i]);
vx.pb(b[i]);
}
for (int i = 1; i <= k; i++) {
cin >> t[i];
vx.pb(t[i]);
}
sort(all(vx));
vx.resize(distance(vx.begin(), unique(all(vx))));
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(all(vx), a[i]) - vx.begin() + 1;
b[i] = lower_bound(all(vx), b[i]) - vx.begin() + 1;
}
kek.init(sz(vx));
vector<pair<int, int> > st;
for (int i = 1; i <= k; i++) {
int uk = lower_bound(all(vx), t[i]) - vx.begin() + 1;
kek.upd(uk, i);
st.pb({uk, i});
}
sort(all(st));
for (int i = 1; i <= n; i++) {
p[i] = {a[i], b[i]};
}
sort(p + 1, p + n + 1, [](pair<int, int> a, pair<int, int> b){return max(a.first, a.second) > max(b.first, b.second);});
long long ans = 0;
ordered_set certain;
for (int i = 1; i <= n; i++) {
int mn = min(p[i].first, p[i].second);
int mx = max(p[i].first, p[i].second);
while (sz(st) && st.back().first >= mx){
certain.insert(st.back().second);
st.pop_back();
}
int lastBetween = kek.get(mn, mx - 1);
int remainingFlip = (sz(certain) - certain.order_of_key(lastBetween)) % 2;
int id;
if (lastBetween == -INF) {
id = (remainingFlip ? p[i].second: p[i].first);
} else {
id = (remainingFlip ? mn: mx);
}
// cout << id << endl;
ans += vx[id];
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
