#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct xy { long long x, y; }a[212121],qr[212121];
bool sort_x(xy a, xy b) { if (a.x != b.x)return a.x < b.x; return a.y < b.y; }
long long Q[212121], ALL[414141], an, tn, tree[212121], P[212121];
vector<int>T[212121], R;
long long oper(long long a, long long b, long long tp) {if (tp == 1) { if (a < b)return b; return a; }else return a + b;}
void insert_g(long long w, long long g, long long tp) { for (long long i = w + tn; i > 0; i /= 2)tree[i] = oper(tree[i], g, tp); }
long long search_g(long long ss, long long ee,long long tp) {
long long s = ss + tn, e = ee + tn, res = tp==1?-1:0;
while (s <= e) {
if (s % 2 == 1)res = oper(res, tree[s++],tp);
if (e % 2 == 0)res = oper(res, tree[e--],tp);
s /= 2; e /= 2;
}
return res;
}
int main() {
long long n, m, i, j; scanf("%lld%lld", &n, &m);
for (i = 0; i < n; i++)scanf("%lld%lld", &a[i].x, &a[i].y), ALL[an++] = a[i].x, ALL[an++] = a[i].y;
for (i = 0; i < m; i++)scanf("%lld", &Q[i]), ALL[an++] = Q[i];
sort(ALL, ALL + an);
an = unique(ALL, ALL + an) - ALL;
for (i = 0; i < n; i++)a[i] = { lower_bound(ALL, ALL + an, a[i].x) - ALL,lower_bound(ALL, ALL + an, a[i].y) - ALL };
for (i = 0; i < m; i++)Q[i] = lower_bound(ALL, ALL + an, Q[i]) - ALL;
for (i = 0; i < m; i++)qr[i] = { Q[i],i };
for (tn = 1; tn < an; tn *= 2);
for (i = 0; i < tn * 2; i++)tree[i] = -1;
sort(qr, qr + m,sort_x);
for (i = 0; i < m; i++)insert_g(qr[i].x, qr[i].y,1);
for (i = 0; i < n; i++) {
long long s = min(a[i].x, a[i].y), e = max(a[i].x, a[i].y);
P[i] = search_g(s, e - 1,1);
if (P[i] == -1)R.push_back(i);
else T[P[i]].push_back(i);
}
for (i = 0; i < tn * 2; i++)tree[i] = 0;
long long ans = 0;
for (i = m - 1; i > 0; i--) {
for (j = 0; j < T[i].size(); j++) {
long long now = T[i][j];
if (search_g(max(a[now].x, a[now].y), an - 1, 0) % 2 == 0)ans += ALL[max(a[now].x, a[now].y)];
else ans += ALL[min(a[now].x, a[now].y)];
}
insert_g(Q[i], 1, 0);
}
for (i = 0; i < R.size(); i++) {
long long now = R[i];
if (search_g(max(a[now].x, a[now].y), an - 1, 0) % 2 == 0)ans += ALL[a[now].x];
else ans += ALL[a[now].y];
}
printf("%lld", ans);
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:42:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < T[i].size(); j++) {
~~^~~~~~~~~~~~~
fortune_telling2.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < R.size(); i++) {
~~^~~~~~~~~~
fortune_telling2.cpp:21:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
long long n, m, i, j; scanf("%lld%lld", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:22:80: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 0; i < n; i++)scanf("%lld%lld", &a[i].x, &a[i].y), ALL[an++] = a[i].x, ALL[an++] = a[i].y;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:23:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 0; i < m; i++)scanf("%lld", &Q[i]), ALL[an++] = Q[i];
~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5368 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5368 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5368 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
