/*input
5 3
4 6
9 1
8 8
4 2
3 7
8 2 9
*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int N = 600005;
int bit[N], Last[N], On[N], Arr[N][20], n, k;
pair<int, int> Query[N], a[N];
map<int, int> Label;
void update(int index, int val){
while(index < N) bit[index] += val, index += index & (-index);
}
int get(int index){
int res = 0;
while(index > 0) res += bit[index], index -= index & (-index);
return res;
}
int Rmq(int l, int r){
if(l > r) return 0;
int dist = (int)log2(r - l + 1);
return max(Arr[l][dist], Arr[r - (1 << dist) + 1][dist]);
}
int main(){
cin >> n >> k;
for(int i = 1; i <= n; ++i){
cin >> a[i].first >> a[i].second;
Label[a[i].first] = 1, Label[a[i].second] = 1;
}
sort(a + 1, a + n + 1, [&](pair<int, int> &x, pair<int, int> &y){
if(max(x.first, x.second) != max(y.first, y.second))
return max(x.first, x.second) < max(y.first, y.second);
return min(x.first, x.second) < min(y.first, y.second);
});
for(int i = 1; i <= n; ++i){
On[i] = (a[i].first > a[i].second);
if(On[i] == 0) swap(a[i].first, a[i].second);
}
Query[k + 1] = make_pair(1000000007, 0);
for(int i = 1; i <= k; ++i){
cin >> Query[i].first;
Query[i].second = i;
Label[Query[i].first] = 1;
}
sort(Query + 1, Query + k + 1);
int cnt = 0;
for(auto it = Label.begin(); it != Label.end(); ++it)
it->second = ++cnt;
for(int i = 1; i <= k; ++i)
Arr[Label[Query[i].first]][0] = Query[i].second;
for(int j = 1; (1 << j) < 3 * N; ++j)
for(int i = 1; i < 3 * N; ++i)
Arr[i][j] = max(Arr[i][j - 1], Arr[min(i + (1 << (j - 1)), N - 1)][j - 1]);
for(int i = 1; i <= n; ++i){
int l = Label.lower_bound(a[i].second)->second;
int r = (--Label.lower_bound(a[i].first))->second;
Last[i] = Rmq(l, r);
}
int64_t l = 1, ans = 0;
for(int i = 1; i <= n; ++i){
while(Query[l].first < a[i].first) update(Query[l++].second, 1);
if(Last[i] != 0) On[i] = 1 ^ ((k - Last[i] - (get(N - 1) - get(Last[i]))) & 1);
else On[i] ^= (k - get(N - 1)) & 1;
ans += On[i] ? a[i].first : a[i].second;
}
cout << ans << endl;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:70:78: warning: iteration 600004u invokes undefined behavior [-Waggressive-loop-optimizations]
Arr[i][j] = max(Arr[i][j - 1], Arr[min(i + (1 << (j - 1)), N - 1)][j - 1]);
^
fortune_telling2.cpp:69:20: note: containing loop
for(int i = 1; i < 3 * N; ++i)
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
65448 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
66768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
433 ms |
75612 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
