#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
class segment_tree
{
#define lc id << 1
#define rc id << 1 | 1
vector<int> ST;
public:
segment_tree(int n)
{
ST.assign(4 * n + 5, 0);
}
void update(int id, int l, int r, int pos, int val)
{
if (l > pos || r < pos) return;
if (l == r){
ST[id] = val;
return;
}
int mid = (l + r) / 2;
update(lc, l, mid, pos, val); update(rc, mid + 1, r, pos, val);
ST[id] = max(ST[lc], ST[rc]);
}
int query(int id, int l, int r, int L, int R)
{
if (l > R || L > r) return 0;
if (L <= l && r <= R) return ST[id];
int mid = (l + r) / 2;
return max(query(lc, l, mid, L, R), query(rc, mid + 1, r, L, R));
}
};
class fenwick_tree
{
vector<int> cnt; int n;
public:
fenwick_tree(int _n)
{
n = _n;
cnt.assign(n + 5, 0);
}
void update(int i, int v)
{
for (; i; i -= i & -i){
cnt[i] += v;
}
}
int sum(int i)
{
int res = 0;
for (; i <= n; i += i & -i){
res += cnt[i];
}
return res;
}
};
int N, M;
int a[maxn], b[maxn], c[maxn];
vector<int> val;
vector<int> query[maxn];
int compress(int x)
{
return lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
}
signed main(void)
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen("A.INP", "r")){
freopen("A.INP", "r", stdin);
freopen("A.OUT", "w", stdout);
}
cin >> N >> M;
for (int i = 1; i <= N; ++i){
cin >> a[i] >> b[i];
val.pb(a[i]); val.pb(b[i]);
}
for (int i = 1; i <= M; ++i){
cin >> c[i];
val.pb(c[i]);
}
sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end());
segment_tree ST(val.size());
fenwick_tree FT(val.size());
for (int i = 1; i <= M; ++i){
c[i] = compress(c[i]);
ST.update(1, 1, maxn, c[i], i);
}
ll res = 0;
for (int i = 1; i <= N; ++i){
if (a[i] == b[i]){
res += a[i];
continue;
}
a[i] = compress(a[i]);
b[i] = compress(b[i]);
int t = ST.query(1, 1, maxn, min(a[i], b[i]), max(a[i], b[i]) - 1);
if (t && a[i] < b[i]) swap(a[i], b[i]);
query[t].pb(i);
}
for (int i = M; i >= 0; --i){
for (auto id : query[i]){
int v = FT.sum(max(a[id], b[id]));
if (v & 1) swap(a[id], b[id]);
res += val[a[id] - 1];
}
if (i) FT.update(c[i], 1);
}
cout << res << '\n';
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:82:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("A.INP", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("A.OUT", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
10104 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
10104 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
10104 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
