• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# po, navarro...

a guest Sep 21st, 2019 141 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. using namespace std;
3.
4. #define st first
5. #define nd second
6. #define mp make_pair
7. #define pb push_back
8. #define cl(x, v) memset((x), (v), sizeof(x))
9.
10. #define db(x) cerr << #x << " == " << x << endl
11. #define dbs(x) cerr << x << endl
12. #define _ << ", " <<
13.
14. typedef long long ll;
15. typedef long double ld;
16.
17. typedef pair<int, int> pii;
18. typedef pair<pii, pii> p4i;
19. typedef pair<int, pii> piii;
20. typedef pair<ll, ll> pll;
21. typedef vector<int> vi;
22.
23. const ld EPS = 1e-9, PI = acos(-1.);
24. const int INF = 0x3f3f3f3f, MOD = 1e9+7;
25. const int N = 1e5+5, P = 1e6+5;
26.
27. int n, m, x[N], y[N], rx[N][2], ry[N][2], ans[N];
28. vector<piii> v;
29. int bit[P];
30.
31. void addp(int p, int v) { for (p+=2; p<P; p+=p&-p) bit[p] += v; }
33. void rem(int l, int r) { addp(l+1, -1); addp(r, 1); }
34.
35. int query(int p) {
36.   int sum = 0;
37.   for (p+=2; p; p-=p&-p) sum += bit[p];
38.   return sum;
39. }
40.
41. int main() {
42.   scanf("%d%d", &n, &m);
43.   vi cc;
44.   for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]), v.pb({ x[i], { 0, i }}), cc.pb(y[i]);
45.   for (int i = 0; i < m; i++) {
46.     scanf("%d%d%d%d", &rx[i][0], &ry[i][0], &rx[i][1], &ry[i][1]);
47.     v.pb({ rx[i][0], { 1, i }});
48.     v.pb({ rx[i][1], { -1, i }});
49.     cc.pb(ry[i][0]); cc.pb(ry[i][1]);
50.   }
51.   sort(v.begin(), v.end());
52.
53.   sort(cc.begin(), cc.end());
54.   cc.erase(unique(cc.begin(), cc.end()), cc.end());
55.   for (int i = 0; i < n; i++) y[i] = lower_bound(cc.begin(), cc.end(), y[i])-cc.begin();
56.   for (int i = 0; i < m; i++)
57.     ry[i][0] = lower_bound(cc.begin(), cc.end(), ry[i][0])-cc.begin(),
58.     ry[i][1] = lower_bound(cc.begin(), cc.end(), ry[i][1])-cc.begin();
59.
60.   for (auto k : v) {
61.     int i = k.nd.nd;
62.     //db(k.st _ k.nd.st _ k.nd.nd);
63.     if (k.nd.st == 0) ans[i] = query(y[i]);
64.     else if (k.nd.st == -1) rem(ry[i][0], ry[i][1]);