Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Sergey Kopeliovich (burunduk30@gmail.com)
- */
- #include <bits/stdc++.h>
- using namespace std;
- #define forn(i, n) for (int i = 0; i < (int)(n); i++)
- #define all(p) p.begin(), p.end()
- int main() {
- int n;
- cin >> n;
- vector<pair<int, int>> p(n);
- forn(i, n)
- cin >> p[i].first >> p[i].second;
- sort(all(p));
- vector<int> t[2 * n]; // [n,2n)
- forn(i, n)
- t[i + n] = {p[i].second};
- for (int i = n - 1; i > 0; i--) {
- t[i].resize(t[i * 2].size() + t[i * 2 + 1].size());
- merge(all(t[2 * i]), all(t[2 * i + 1]), t[i].begin());
- }
- auto inner_get = [&](int i, int y1, int y2) {
- return upper_bound(all(t[i]), y2) - lower_bound(all(t[i]), y1);
- };
- auto get = [&](int x1, int x2, int y1, int y2) {
- int l = lower_bound(all(p), make_pair(x1, y1)) - p.begin();
- int r = upper_bound(all(p), make_pair(x2, y2)) - p.begin() - 1;
- int sum = 0;
- for (l += n, r += n; l <= r; l /= 2, r /= 2) {
- if (l % 2 == 1) sum += inner_get(l++, y1, y2);
- if (r % 2 == 0) sum += inner_get(r--, y1, y2);
- }
- return sum;
- };
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement