#include<cstdio>
#include<algorithm>
#include<vector>
#define SZ 524288
using namespace std;
int n, K;
struct point {
int a, b;
}w[201000], ori[201000];
int X[401000], P[201000], Q[201000], IT[SZ+SZ];
vector<int>G[401000];
int BIT[SZ];
void Ins(int a, int b) {
a += SZ;
while (a) {
IT[a] = max(IT[a], b);
a >>= 1;
}
}
void Add(int a, int b) {
while (a < SZ) {
BIT[a] += b;
a += (a&-a);
}
}
int Sum(int a) {
int r = 0;
while (a) {
r += BIT[a];
a -= (a&-a);
}
return r;
}
int Max(int b, int e) {
b += SZ, e += SZ;
int r = 0;
while (b <= e) {
r = max(r, max(IT[b], IT[e]));
b = (b + 1) >> 1, e = (e - 1) >> 1;
}
return r;
}
long long res;
int main() {
int i, a;
scanf("%d%d", &n, &K);
for (i = 1; i <= n; i++) {
scanf("%d%d", &w[i].a, &w[i].b);
X[i] = w[i].a, X[n + i] = w[i].b;
ori[i] = w[i];
}
sort(X + 1, X + n + n + 1);
for (i = 1; i <= n; i++) {
w[i].a = lower_bound(X + 1, X + n + n + 1, w[i].a) - X;
w[i].b = lower_bound(X + 1, X + n + n + 1, w[i].b) - X;
}
for (i = 1; i <= K; i++) {
scanf("%d", &a);
a = lower_bound(X + 1, X + n + n + 1, a + 1) - X - 1;
Q[i] = a;
Ins(a, i);
}
for (i = 1; i <= n; i++) {
int mn = min(w[i].a, w[i].b), mx = max(w[i].a, w[i].b);
G[Max(mn,mx-1)].push_back(i);
}
for (i = K; i >= 0; i--) {
for (auto &x : G[i]) {
int ck = ((K - i) - Sum(w[x].b - 1)) % 2;
if (i) {
if (ck)res += min(ori[x].a, ori[x].b);
else res += max(ori[x].a, ori[x].b);
}
else {
if (ck)res += ori[x].b;
else res += ori[x].a;
}
}
if (!i)break;
Add(Q[i], 1);
}
printf("%lld\n", res);
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:46: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:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &w[i].a, &w[i].b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
9848 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
9848 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
9848 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
