#include <bits/stdc++.h> #define FOR(i, x, y) for (int i = x; i < y; i++) typedef long long ll; using namespace std; pair<int, int> a[200001]; int t[200001], segtree[2400001], bit[600001]; vector<pair<int, int>> c; bool inv[200001], visited[200001]; void build(int node = 1, int l = 1, int r = c.size()) { if (l == r) segtree[node] = c[l - 1].second ? 0 : l; else { int mid = (l + r) / 2; build(node * 2, l, mid); build(node * 2 + 1, mid + 1, r); segtree[node] = max(segtree[node * 2], segtree[node * 2 + 1]); } } int rmq(int x, int y, int node = 1, int l = 1, int r = c.size()) { if (l > y || r < x) return 0; if (l >= x && r <= y) return segtree[node]; int mid = (l + r) / 2; return max(rmq(x, y, node * 2, l, mid), rmq(x, y, node * 2 + 1, mid + 1, r)); } void add(int pos) { for (; pos <= c.size(); pos += (pos & (-pos))) bit[pos]++; } int rsq(int x, int y) { int ans = 0; for (; y; y -= (y & (-y))) ans += bit[y]; for (x--; x; x -= (x & (-x))) ans -= bit[x]; return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; FOR(i, 1, n + 1) { cin >> a[i].first >> a[i].second; inv[i] = a[i].first < a[i].second; if (inv[i]) swap(a[i].first, a[i].second); c.push_back({a[i].first, i}); c.push_back({a[i].second, -i}); } FOR(i, 1, q + 1) { cin >> t[i]; c.push_back({t[i], 0}); } sort(c.begin(), c.end()); c.erase(unique(c.begin(), c.end()), c.end()); build(); FOR(i, 1, n + 1) { a[i].first = lower_bound(c.begin(), c.end(), make_pair(a[i].first, i)) - c.begin() + 1; a[i].second = lower_bound(c.begin(), c.end(), make_pair(a[i].second, -i)) - c.begin() + 1; } // for (pair<int, int> i : c) cout << i.first << ' ' << i.second << " | "; // cout << '\n'; // FOR(i, 1, c.size() + 1) cout << rmq(i, i) << ' '; // cout << '\n'; ll ans = 0; for (int i = c.size() - 1; i; i--) { int k = c[i].second; if (k) { if (visited[abs(k)]) continue; visited[k] = true; int cnt = rsq(rmq(a[k].second, a[k].first) + 1, c.size()); // cout << cnt - inv[k] << ' ' << k << " HERE\n"; // cout << a[k].second << ' ' << a[k].first << ' ' << rmq(a[k].second, a[k].first) << '\n'; if (cnt & 1) ans += c[a[k].first - 1].first; else ans += c[a[k].second - 1].first; // cout << ans << '\n'; } else add(i); } cout << ans; return 0; }

fortune_telling2.cpp: In function 'void add(int)':
fortune_telling2.cpp:28:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 void add(int pos) { for (; pos <= c.size(); pos += (pos & (-pos))) bit[pos]++; }
                            ~~~~^~~~~~~~~~~