Cod sursa(job #2628806)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 17 iunie 2020 16:36:48
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("pachete.in");
ofstream fout("pachete.out");

const int nmax = 50000;
int n, x, y, z1, z2, z3, z4, v[nmax + 5];

struct cadran
{
    int x, y;
}c1[nmax + 5], c2[nmax + 5], c3[nmax + 5], c4[nmax + 5];

bool cmp(cadran a, cadran b)
{
    if (a.x == b.x)
        return a.y < b.y;
    else
        return a.x < b.x;
}

int cbin(int z, int x)
{
    int st = 1, dr = z, ans = -1;
    while (st <= dr)
    {
        int mid = (st + dr) / 2;
        if (x >= v[mid])
        {
            ans = mid;
            dr = mid - 1;
        }
        else
        {
            st = mid + 1;
        }
    }
    return ans;
}
int solve(cadran *c, int z)
{
    if (z == 0) return 0;
    int k = 1;
    v[k] = c[1].y;
    for (int i = 2; i <= z; ++i)
    {
        int poz = cbin(k, c[i].y);
        if (poz == -1)
        {
            v[++k] = c[i].y;
        }
        else
        {
            v[poz] = c[i].y;
        }
    }
    return k;
}

int main()
{
    fin >> n >> x >> y;
    for (int i = 1; i <= n; ++i)
    {
        int xx, yy;
        fin >> xx >> yy;
        if (xx <= x && yy >= y) c1[++z1] = {-xx, yy};
        else if (xx > x && yy > y) c2[++z2] = {xx, yy};
        else if (xx < x && yy < y) c3[++z3] = {-xx, -yy};
        else c4[++z4] = {xx, -yy};
    }
    sort(c1 + 1, c1 + z1 + 1, cmp);
    sort(c2 + 1, c2 + z2 + 1, cmp);
    sort(c3 + 1, c3 + z3 + 1, cmp);
    sort(c4 + 1, c4 + z4 + 1, cmp);
    fout << solve(c1, z1) + solve(c2, z2) + solve(c3, z3) + solve(c4, z4);
    fin.close();
    fout.close();
    return 0;
}