#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
struct card {
int a, b, t;
void scan() {
scanf("%d%d", &a, &b);
if (a > b) swap(a, b), t = 1;
else t = 0;
}
bool operator<(const card &c) const {
return a < c.a;
}
};
const int MAXN = 2e5 + 1;
int n, k;
card cs[MAXN];
int t[MAXN];
pii ct[MAXN];
int segm[1 << 19];
int segs[1 << 19];
int queryMax(int i, int s, int e, int x) {
if (x <= segm[i]) return 0;
if (s == e) return s;
int m = (s + e) / 2;
int ret = queryMax(i << 1 | 1, m + 1, e, x);
if (ret) return ret;
return queryMax(i << 1, s, m, x);
}
void update(int i, int s, int e, int x, int v) {
if (s == e) {
segm[i] = v;
++segs[i];
return;
}
int m = (s + e) / 2;
if (x <= m) update(i << 1, s, m, x, v);
else update(i << 1 | 1, m + 1, e, x, v);
segm[i] = min(segm[i << 1], segm[i << 1 | 1]);
segs[i] = segs[i << 1] + segs[i << 1 | 1];
}
int querySum(int i, int s, int e, int x, int y) {
if (e < x || y < s) return 0;
if (x <= s && e <= y) return segs[i];
int m = (s + e) / 2;
return querySum(i << 1, s, m, x, y) + querySum(i << 1 | 1, m + 1, e, x, y);
}
const int inf = 1e9 + 7;
int main() {
for (int i = 0; i < (1 << 19); ++i) segm[i] = inf;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; ++i) {
cs[i].scan();
}
for (int i = 1; i <= k; ++i) {
scanf("%d", t + i);
ct[i - 1] = { t[i], i };
}
sort(cs, cs + n);
sort(ct, ct + k, greater<pii>());
llong ans = 0;
for (int i = 0, j = 0; i < n; ++i) {
while (j < k && cs[i].a <= ct[j].first) {
update(1, 1, k, ct[j].second, ct[j].first);
++j;
}
int x = queryMax(1, 1, k, cs[i].b);
if (x) cs[i].t = 1;
int cnt = querySum(1, 1, k, x + 1, k) % 2;
if (cnt ^ cs[i].t) ans += cs[i].b;
else ans += cs[i].a;
}
printf("%lld\n", ans);
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:73:10: 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:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", t + i);
~~~~~^~~~~~~~~~~~~
fortune_telling2.cpp: In member function 'void card::scan()':
fortune_telling2.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
