#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
const int MAXN = 1 << 20;
struct segtree {
int tr[2 * MAXN];
segtree() {
for (int i = 0; i < 2 * MAXN; i++) {
tr[i] = -1e9;
}
}
void update (int x, int v) {
x += MAXN;
tr[x] = v;
while (x >>= 1) {
tr[x] = max(tr[2 * x], tr[2 * x + 1]);
}
}
int query (int a, int b, int cur = 1, int lt = 0, int rt = MAXN) {
if (rt <= a || b <= lt) {
return -1e9;
}
if (a <= lt && rt <= b) {
return tr[cur];
}
int mid = (lt + rt) / 2;
return max(query(a, b, 2 * cur, lt, mid), query(a, b, 2 * cur + 1, mid, rt));
}
};
int N, K;
vector<pii> card;
vector<int> T;
vector<int> vals;
segtree seg = segtree();
int main() {
scanf("%d %d", &N, &K);
card.resize(N);
T.resize(K);
for (int i = 0; i < N; i++) {
scanf("%d %d", &card[i].fi, &card[i].se);
vals.push_back(card[i].fi);
vals.push_back(card[i].se);
}
for (int i = 0; i < K; i++) {
scanf("%d", &T[i]);
vals.push_back(T[i]);
}
sort(all(vals));
vals.resize(unique(all(vals)) - vals.begin());
for (int i = 0; i < N; i++) {
card[i].fi = lower_bound(all(vals), card[i].fi) - vals.begin();
card[i].se = lower_bound(all(vals), card[i].se) - vals.begin();
T[i] = lower_bound(all(vals), T[i]) - vals.begin();
}
vector<pii> vt;
for (int i = 0; i < K; i++) {
seg.update(T[i], i);
vt.push_back({T[i], i});
}
sort(all(vt));
sort(all(card), [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
oset<int> certain; //ones that are certainly going to flip the card
ll ans = 0;
for (int i = 0; i < N; i++) {
int mnside = min(card[i].fi, card[i].se), mxside = max(card[i].fi, card[i].se);
while (!vt.empty() && vt.back().fi >= mxside) {
certain.insert(vt.back().se);
vt.pop_back();
}
int x = seg.query(mnside, mxside); //KEY IDEA: "maybe" is going to turn the card to the min. so certainly the last "maybe" will.
bool flip = (certain.size() - certain.order_of_key(x)) % 2;
int ind;
if (x == -1e9) {
ind = (flip ? card[i].se : card[i].fi);
} else {
ind = (flip ? mnside : mxside);
}
ans += vals[ind];
}
printf("%lld\n", ans);
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &K);
~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &card[i].fi, &card[i].se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &T[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
16888 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 |
19 ms |
16888 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 |
19 ms |
16888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
