#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
const ll SIZE = 2e5 + 10, INF = 1e9 * 1e9;
vector<pair<ll, ll>> vec;
vector<ll> vc;
vector<ll> tree[SIZE * 4];
void build(int v, int l, int r) {
if (l == r - 1) {
tree[v].push_back(vc[l]);
}
else {
int mid = (l + r) / 2;
build(v * 2 + 1, l, mid);
build(v * 2 + 2, mid, r);
merge(tree[v * 2 + 1].begin(), tree[v * 2 + 1].end(), tree[v * 2 + 2].begin(), tree[v * 2 + 2].end(), std::back_inserter(tree[v]));
}
}
ll get(int v, int l, int r, int askl, int askr, ll minVal, ll maxVal) {
if (l >= askr || r <= askl) return 0;
if (l >= askl && r <= askr) {
ll mr = upper_bound(tree[v].begin(), tree[v].end(), maxVal) - tree[v].begin();
ll lw = lower_bound(tree[v].begin(), tree[v].end(), minVal) - tree[v].begin();
return mr - lw;
}
int mid = (l + r) / 2;
return get(v * 2 + 1, l, mid, askl, askr, minVal, maxVal) + get(v * 2 + 2, mid, r, askl, askr, minVal, maxVal);
}
ll get2(int v, int l, int r, int askl, int askr, int minVal, int maxVal) {
if (l == r - 1) {
return l;
}
else {
int mid = (l + r) / 2;
ll mr = upper_bound(tree[v * 2 + 2].begin(), tree[v * 2 + 2].end(), maxVal) - tree[v * 2 + 2].begin();
ll lw = lower_bound(tree[v * 2 + 2].begin(), tree[v * 2 + 2].end(), minVal) - tree[v * 2 + 2].begin();
if (mr - lw >= 1) {
return get2(v * 2 + 2, mid, r, askl, askr, minVal, maxVal);
}
else {
return get2(v * 2 + 1, l, mid, askl, askr, minVal, maxVal);
}
}
}
int main() {
fastInp;
ll n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
ll a, b;
cin >> a >> b;
vec.push_back({ a, b });
}
vc.push_back(-1);
for (int i = 0; i < k; i++) {
ll x;
cin >> x;
vc.push_back(x);
}
build(0, 0, vc.size());
ll s = 0;
for (int i = 0; i < n; i++) {
if (vec[i].first == vec[i].second) {
s += vec[i].first;
continue;
}
ll mn = min(vec[i].first, vec[i].second), mx = max(vec[i].first, vec[i].second);
ll ind = get2(0, 0, vc.size(), 0, vc.size(), mn, mx - 1);
if (ind == 0) {
if (vec[i].first > vec[i].second) swap(vec[i].first, vec[i].second);
}
if (ind + 1 == vc.size()) {
s += mx;
continue;
}
ll cnt = get(0, 0, vc.size(), ind + 1, vc.size(), mx, INF);
if (cnt % 2 == 0) {
s += vec[i].first;
}
else {
s += vec[i].second;
}
}
cout << s;
return 0;
}
//1 7
//2 9
//1
//4
//5
//9
//0
//12
//15
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:101:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ind + 1 == vc.size()) {
~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
