Cod sursa(job #2302481)

Utilizator akaprosAna Kapros akapros Data 14 decembrie 2018 18:29:51
Problema Cadrane Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.18 kb
#include <bits/stdc++.h>
#define maxN 100002
#define inf 1000000000
using namespace std;

FILE *fin = freopen("cadrane.in", "r", stdin);
FILE *fout = freopen("cadrane.out", "w", stdout);

/* ----------------------------------- */
int n;
struct Point
{
    int x, y, id;
    bool operator < (const Point &ot) const
    {
        if (x == ot.x)
            return y < ot.y;
        return x < ot.x;
    }
} m, M, v[maxN];

struct Node
{
    int size;
    int val;
    Node* left;
    Node* right;
};
Node* emptyNode = new Node();
Node* root0, *root1;

int ans;

/*class SegTree
{
public :*/
void update(Node *nod, int l, int r, int pos, int val)
{
    if (l > r || l > pos || r < pos)
        return ;
    if (l == r)
    {
        nod->val += val;
        return ;
    }
    int mid = (l + r) >> 1;
    if (r > mid)
    {
        if (nod->left == emptyNode)
        {
            nod->left = new Node();
            nod->left->right = nod->left->left = emptyNode;
        }
        update(nod->left, l, mid, pos, val);
    }
    else
    {
        if (nod->right == emptyNode)
        {
            nod->right = new Node();
            nod->right->right = nod->right->left = emptyNode;
        }
        update(nod->right, mid + 1, r, pos, val);
    }
    nod->val = nod->left->val + nod->right->val;
}
int query(Node *nod, int l, int r, int lu, int ru)
{
    if (l > r || l > ru || r < lu)
        return 0;
    if (lu <= l && ru >= r)
        return nod->val;
    int mid = (l + r) >> 1, q1 = 0, q2 = 0;
    if (lu <= mid)
    {
        if (nod->left == emptyNode)
            q1 = 0;
        else
            q1 = query(nod->left, l, mid, lu, ru);
    }
    if (ru > mid)
    {
        if (nod->right == emptyNode)
            q2 = 0;
        else
            q2 = query(nod->right, l, mid, lu, ru);
    }
    return q1 + q2;
}
void init()
{
    emptyNode->val = 0;
    emptyNode->left = emptyNode->right = emptyNode;
    root0 = new Node();
    root0->val = 0;
    root0->left = root0->right = emptyNode;

    root1 = new Node();
    root1->val = 0;
    root1->left = root1->right = emptyNode;
}
//} T;
void sweep()
{
    for (int i = 1; i <= n; ++ i)
    {
        int j = i;
        while (v[i].x == v[j].x)
        {
            update(root0, m.y, M.y, v[j].y, 1);
            ++ j;
        }
        for (; j > i; -- j)
        {
            ans = max(ans, query(root0, m.y, M.y, m.y, v[j - 1].y) +
                      query(root1, m.y, M.y, v[j - 1].y, M.y));
        }
        while (v[i].x == v[j].x)
        {
            update(root1, m.y, M.y, v[j].y, 1);
            ++ j;
        }
        i = j - 1;
    }
}

int main()
{
    init();
    scanf("%d", &n);
    m = {inf, inf};
    M = {0, 0};
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%d%d", &v[i].x, &v[i].y);
        v[i].id = i;
        M.x = max(M.x, v[i].x);
        M.y = max(M.y, v[i].y);
        m.x = min(m.x, v[i].x);
        m.y = min(m.y, v[i].y);
    }
    sort(v + 1, v + n + 1);
    for (int i = 1; i <= n; ++ i)
        update(root1, m.y, M.y, v[i].y, 1);
    sweep();
    printf("%d\n", ans);
    return 0;
}