#include <bits/stdc++.h>
using namespace std;
struct SGT{
int n;
vector<int> tree;
SGT(int n) :n(n) {
tree = vector<int>(n * 4, -1);
}
void update(int idx, int val, int nodele, int noderi, int node) {
if (idx < nodele || noderi < idx)return;
if (nodele == noderi) {
tree[node] = val;
return;
}
int mid = (nodele + noderi) / 2;
update(idx, val, nodele, mid, node * 2);
update(idx, val, mid + 1, noderi, node * 2 + 1);
}
void update(int idx, int val) {
update(idx, val, 0, n - 1, 1);
}
int query(int le, int ri, int nodele, int noderi, int node) {
if (ri<nodele || le>noderi)return -1;
if (le <= nodele && noderi <= ri)return tree[node];
int mid = (nodele + noderi) / 2;
return max(query(le, ri, nodele, mid, node * 2), query(le, ri, mid + 1, noderi, node * 2 + 1));
}
int query(int le, int ri) {
return query(le, ri, 0, n - 1, 1);
}
};
struct SGT2 {
int n;
vector<vector<int> >tree;
SGT2(int n,int arr[]) :n(n) {
tree = vector<vector<int> >(n * 4);
init(arr, 0, n - 1, 1);
}
void init(int arr[], int le, int ri, int node) {
if (le == ri) {
tree[node].push_back(arr[le]);
return;
}
int mid = (le + ri) / 2;
init(arr, le, mid, node * 2);
init(arr, mid + 1, ri, node * 2 + 1);
for (auto x : tree[node * 2])
tree[node].push_back(x);
for (auto x : tree[node * 2 + 1])
tree[node].push_back(x);
sort(tree[node].begin(), tree[node].end());
}
int query(int le, int ri,int val, int nodele, int noderi, int node) {
if (ri<nodele || le>noderi)return 0;
if (le <= nodele && noderi <= ri)return tree[node].size() - (lower_bound(tree[node].begin(), tree[node].end(), val) - tree[node].begin());
int mid = (nodele + noderi) / 2;
return query(le, ri,val, nodele, mid, node * 2)+query(le, ri,val, mid + 1, noderi, node * 2 + 1);
}
int query(int le, int ri,int val) {
return query(le, ri, val, 0, n - 1, 1);
}
};
int n, k;
pair<int, int> arr[200005];
int t[200005];
vector<int> xidx;
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%d%d", &arr[i].first, &arr[i].second);
xidx.push_back(arr[i].first);
xidx.push_back(arr[i].second);
}
for (int i = 0; i < k; i++) {
scanf("%d", &t[i]);
xidx.push_back(t[i]);
}
sort(xidx.begin(), xidx.end());
xidx.erase(unique(xidx.begin(), xidx.end()), xidx.end());
SGT sgt(xidx.size());
SGT2 sgt2(k, t);
for (int i = 0; i < k; i++) {
int idx = lower_bound(xidx.begin(), xidx.end(), t[i]) - xidx.begin();
sgt.update(idx, i);
}
long long ans = 0;
for (int i = 0; i < n; i++) {
int a = min(arr[i].first, arr[i].second);
int b = max(arr[i].first, arr[i].second);
int idx = sgt.query(lower_bound(xidx.begin(), xidx.end(), a) - xidx.begin(), lower_bound(xidx.begin(), xidx.end(), b) - xidx.begin() - 1);
int cnt = sgt2.query(idx + 1, k - 1, b);
if (idx >= 0)ans += (cnt & 1 ? a : b);
else ans += (cnt & 1 ? arr[i].second : arr[i].first);
}
printf("%lld\n", ans);
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:69: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:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &arr[i].first, &arr[i].second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
