MRECT1 - Điểm trên cạnh hình chữ nhật - HRASTOVI

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
//#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 700005;
using namespace std;

int n, m, p;
int x1[N], y1[N], x2[N], y2[N];

struct point {
    int x, y, id;
    point(int _x = 0, int _y = 0, int _id = 0) {
        x = _x; y = _y; id = _id;
    }
    bool operator < (const point &b) const {
        return (x != b.x) ? (x < b.x) : ((y != b.y) ? (y < b.y) : id < b.id);
    }
} a[N];

int findLeft(point a) {
    if (a.y == y1[a.id]) return -1;
    return y1[a.id];
}

int s[N];
int ans[N];

void solve() {
    sort(a + 1, a + 1 + p);
    int j;
    for(int i = 1; i <= p; i = j + 1) {
        j = i;
        while (a[j + 1].x == a[i].x) j++;
        s[i - 1] = 0;
        REP(k, i, j) {
            s[k] = s[k - 1];
            if (a[k].id) {
                int l = i, r = k, pos;
                int leftBound = findLeft(a[k]);
                if (leftBound == -1) continue;
                while (l <= r) {
                    int mid = l + r >> 1;
                    if (a[mid].y >= leftBound) {
                        pos = mid; r = mid - 1;
                    }
                    else
                        l = mid + 1;
                }
                ans[a[k].id] += s[k] - s[pos - 1];
            }
            else
                s[k]++;
        }
    }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    REP(i, 1, n) cin >> a[i].x >> a[i].y;
    cin >> m;
    p = n;
    REP(i, 1, m) {
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
        a[++p] = point(x1[i], y1[i], i);
        a[++p] = point(x1[i], y2[i], i);
        a[++p] = point(x2[i], y1[i], i);
        a[++p] = point(x2[i], y2[i], i);
    }
    solve();
    REP(i, 1, p) swap(a[i].x, a[i].y);
    REP(i, 1, m) {
        int yy1 = y1[i], yy2 = y2[i];
        y1[i] = x1[i]; y2[i] = x2[i];
        x1[i] = yy2; x2[i] = yy1;
    }
    solve();
    int j;
    for(int i = 1; i <= p; i = j + 1) {
        j = i;
        if (a[i].id == 0) {
            while (a[j + 1].x == a[i].x && a[j + 1].y == a[i].y)
                ans[a[++j].id]--;
        }
    }
    REP(i, 1, m) cout << ans[i] << '\n';
    return 0;
}

Download