Cod sursa(job #597764)

Utilizator darrenRares Buhai darren Data 23 iunie 2011 10:58:07
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.33 kb
#include <fstream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

#define x first
#define y second

int N;
pair<int, int> init;
vector<pair<int, int> > V[4];
int last[50002];
int result;

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

    fin >> N;
    fin >> init.x >> init.y;

    for (int i = 1, c1, c2; i <= N; ++i)
    {
        fin >> c1 >> c2;

        if (c1 > init.x && c2 > init.y) V[0].push_back(make_pair(c1, c2));
        else if (c1 > init.x && c2 < init.y) V[1].push_back(make_pair(c1, c2));
        else if (c1 < init.x && c2 > init.y) V[2].push_back(make_pair(c1, c2));
        else if (c1 < init.x && c2 < init.y) V[3].push_back(make_pair(c1, c2));
    }

    // 1

    if (V[0].size())
    {
        sort(V[0].begin(), V[0].end(), less<pair<int, int> >());
        last[0] = 1, last[1] = V[0].front().second;
        for (int i = 1; i < V[0].size(); ++i)
        {
            int step, where;
            for (step = 1; (step << 1) <= last[0]; step <<= 1);
            for (where = 0; step; step >>= 1)
                if (where + step <= last[0] && last[where + step] > V[0][i].second)
                    where += step;
            ++where;

            if (where > last[0]) ++last[0];
            last[where] = V[0][i].second;
        }
        result += last[0];
    }

    // 2

    if (V[1].size())
    {
        sort(V[1].begin(), V[1].end(), less<pair<int, int> >());
        last[0] = 1, last[1] = V[1].front().second;
        for (int i = 1; i < V[1].size(); ++i)
        {
            int step, where;
            for (step = 1; (step << 1) <= last[0]; step <<= 1);
            for (where = 0; step; step >>= 1)
                if (where + step <= last[0] && last[where + step] < V[1][i].second)
                    where += step;
            ++where;

            if (where > last[0]) ++last[0];
            last[where] = V[1][i].second;
        }
        result += last[0];
    }

    // 3

    if (V[2].size())
    {
        sort(V[2].begin(), V[2].end(), greater<pair<int, int> >());
        last[0] = 1, last[1] = V[2].front().second;
        for (int i = 1; i < V[2].size(); ++i)
        {
            int step, where;
            for (step = 1; (step << 1) <= last[0]; step <<= 1);
            for (where = 0; step; step >>= 1)
                if (where + step <= last[0] && last[where + step] > V[2][i].second)
                    where += step;
            ++where;

            if (where > last[0]) ++last[0];
            last[where] = V[2][i].second;
        }
        result += last[0];
    }

    // 4

    if (V[3].size())
    {
        sort(V[3].begin(), V[3].end(), greater<pair<int, int> >());
        last[0] = 1, last[1] = V[3].front().second;
        for (int i = 1; i < V[3].size(); ++i)
        {
            int step, where;
            for (step = 1; (step << 1) <= last[0]; step <<= 1);
            for (where = 0; step; step >>= 1)
                if (where + step <= last[0] && last[where + step] < V[3][i].second)
                    where += step;
            ++where;

            if (where > last[0]) ++last[0];
            last[where] = V[3][i].second;
        }
        result += last[0];
    }

    fout << result;

    fin.close();
    fout.close();
}