#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct xy { int 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; }
int Q[212121], ALL[414141], an, tn, tree[212121], P[212121];
vector<int>T[212121], R;
int oper(int a, int b, int tp) {if (tp == 1) { if (a < b)return b; return a; }else return a + b;}
void insert_g(int w, int g, int tp) { for (int i = w + tn; i > 0; i /= 2)tree[i] = oper(tree[i], g, tp); }
int search_g(int ss, int ee,int tp) {
int 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() {
int n, m, i, j; scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)scanf("%d%d", &a[i].x, &a[i].y), ALL[an++] = a[i].x, ALL[an++] = a[i].y;
for (i = 0; i < m; i++)scanf("%d", &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++) {
int 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++) {
int 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++) {
int 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:26:69: warning: narrowing conversion of '((((long int)std::lower_bound<int*, int>(((int*)(& ALL)), (((int*)(& ALL)) + ((sizetype)(((long unsigned int)an) * 4))), a[i].xy::x)) - ((long int)((int*)(& ALL)))) (ceiling /) 4)' from 'long int' to 'int' inside { } [-Wnarrowing]
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 };
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
fortune_telling2.cpp:26:110: warning: narrowing conversion of '((((long int)std::lower_bound<int*, int>(((int*)(& ALL)), (((int*)(& ALL)) + ((sizetype)(((long unsigned int)an) * 4))), a[i].xy::y)) - ((long int)((int*)(& ALL)))) (ceiling /) 4)' from 'long int' to 'int' inside { } [-Wnarrowing]
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 };
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
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:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, m, i, j; scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:22:76: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 0; i < n; i++)scanf("%d%d", &a[i].x, &a[i].y), ALL[an++] = a[i].x, ALL[an++] = a[i].y;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:23:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 0; i < m; i++)scanf("%d", &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 |
5456 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 |
5456 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 |
5456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
