Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- #define pb push_back
- #define all(a) a.begin(), a.end()
- #define rall(a) a.rbegin(), a.rend()
- #define x first
- #define y second
- void out(vector<int> a) {
- for (auto it = a.begin(); it != a.end(); ++it) cout << (*it) << " ";
- cout << "\n";
- }
- struct sq {
- int ind;
- int x1, y1, x2, y2;
- };
- struct node {
- int l, r, id = -1;
- };
- int n;
- vector<sq> a;
- const int N = 5e5 + 47;
- node tree[4*N];
- inline void read() {
- cin >> n;
- a.resize(n);
- for (int i = 0; i<n; ++i) cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
- }
- bool comp(sq u, sq v) {
- if (u.y1 < v.y1) return true;
- else return false;
- }
- void build(int i, int l, int r) {
- if (l > r) return;
- tree[i].l = l, tree[i].r = r;
- if (l == r) {
- tree[i].id = -1;
- return;
- }
- int mid = (l + r) / 2;
- build(2 * i, l, mid);
- build(2 * i + 1, mid + 1, r);
- }
- void push (int i) {
- if (tree[i].id != -1 && tree[i].l != tree[i].r) {
- tree[2 * i].id = tree[i].id;
- tree[2 * i + 1].id = tree[i].id;
- tree[i].id = -1;
- }
- }
- void upd(int i, int l, int r, int index) {
- push(i);
- if (r < tree[i].l || l > tree[i].r) return;
- if (tree[i].l >= l && tree[i].r <= r) {
- tree[i].id = index;
- return;
- }
- upd(2 * i, l, r, index);
- upd(2 * i + 1, l, r, index);
- }
- int get_id (int i, int index) {
- push(i);
- if (index < tree[i].l || index > tree[i].r) return -1;
- if (tree[i].l == index && tree[i].r == index) return tree[i].id;
- return max(get_id(2 * i, index), get_id(2 * i + 1, index));
- }
- inline void solve() {
- int ans = 0;
- sort(all(a), comp);
- build(1, 0, n - 1);
- for (int i = 0; i<n; ++i) {
- if (get_id(1, a[i].x1) == -1) {
- upd(1, a[i].x1, a[i].x2, a[i].ind);
- ++ans;
- }
- else {
- int j = get_id(1, a[i].x1);
- cout << j << endl;
- if (a[i].x1 >= a[j].x1 && a[i].x1 <= a[j].x2 &&
- a[i].y1 >= a[j].y1 && a[i].y1 <= a[j].y2)
- continue;
- else {
- upd(1, a[i].x1, a[i].x2, a[i].ind);
- ++ans;
- }
- }
- }
- cout << ans;
- }
- signed main() {
- ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
- cout << fixed << setprecision(20);
- //freopen("input.in", "r", stdin);
- //freopen("output.out", "w", stdout);
- read();
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement