Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define st first
- #define nd second
- #define mp make_pair
- #define pb push_back
- #define cl(x, v) memset((x), (v), sizeof(x))
- #define db(x) cerr << #x << " == " << x << endl
- #define dbs(x) cerr << x << endl
- #define _ << ", " <<
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pii;
- typedef pair<pii, pii> p4i;
- typedef pair<int, pii> piii;
- typedef pair<ll, ll> pll;
- typedef vector<int> vi;
- const ld EPS = 1e-9, PI = acos(-1.);
- const int INF = 0x3f3f3f3f, MOD = 1e9+7;
- const int N = 1e5+5, P = 1e6+5;
- int n, m, x[N], y[N], rx[N][2], ry[N][2], ans[N];
- vector<piii> v;
- int bit[P];
- void addp(int p, int v) { for (p+=2; p<P; p+=p&-p) bit[p] += v; }
- void add(int l, int r) { addp(l+1, 1); addp(r, -1); }
- void rem(int l, int r) { addp(l+1, -1); addp(r, 1); }
- int query(int p) {
- int sum = 0;
- for (p+=2; p; p-=p&-p) sum += bit[p];
- return sum;
- }
- int main() {
- scanf("%d%d", &n, &m);
- vi cc;
- for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]), v.pb({ x[i], { 0, i }}), cc.pb(y[i]);
- for (int i = 0; i < m; i++) {
- scanf("%d%d%d%d", &rx[i][0], &ry[i][0], &rx[i][1], &ry[i][1]);
- v.pb({ rx[i][0], { 1, i }});
- v.pb({ rx[i][1], { -1, i }});
- cc.pb(ry[i][0]); cc.pb(ry[i][1]);
- }
- sort(v.begin(), v.end());
- sort(cc.begin(), cc.end());
- cc.erase(unique(cc.begin(), cc.end()), cc.end());
- for (int i = 0; i < n; i++) y[i] = lower_bound(cc.begin(), cc.end(), y[i])-cc.begin();
- for (int i = 0; i < m; i++)
- ry[i][0] = lower_bound(cc.begin(), cc.end(), ry[i][0])-cc.begin(),
- ry[i][1] = lower_bound(cc.begin(), cc.end(), ry[i][1])-cc.begin();
- for (auto k : v) {
- int i = k.nd.nd;
- //db(k.st _ k.nd.st _ k.nd.nd);
- if (k.nd.st == 0) ans[i] = query(y[i]);
- else if (k.nd.st == -1) rem(ry[i][0], ry[i][1]);
- else add(ry[i][0], ry[i][1]);
- }
- for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement