Cod sursa(job #807973)

Utilizator mipsPavel Mircea mips Data 5 noiembrie 2012 23:35:16
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int main()
{
    vector< pair< long long , long long > > puncte[4];
    long long n,x,y;
    fin >> n;
    fin >> x >> y;
    for (long long i=0;i<n;i++)
    {
        long long a,b;
        fin >> a >> b;
        if (a<x)
        {


            if (b<y)
            {
                puncte[0].push_back( make_pair(a,b) );
            }
            else
            {
                puncte[1].push_back( make_pair(a,b) );
            }
        }
        else
        {
            if (b<y)
            {
                puncte[2].push_back( make_pair(a,b) );
            }
            else
            {
                puncte[3].push_back( make_pair(a,b) );
            }
        }
    }
    long long total=0;
    for (long long i=0;i<4;i++)
    {
        sort(puncte[i].begin(),puncte[i].end());
        //cout << "cadran "<<i<<endl;
        //for (long long k=0;k<puncte[i].size();k++)
        //    cout << puncte[i][k].second << " ";
        //    cout << endl;

        vector<long long> ys;
        if (puncte[i].size()>0)
        {
            total++;
            ys.push_back(puncte[i][0].second);
        }
        for (long long j=1;j<puncte[i].size();j++)
        {
            //cout << "value:"<<puncte[i][j].second<< endl;
            //cout << "ys"<< endl;
            //for (long long k=0;k<ys.size();k++)
            //cout << ys[k]<< " ";
            //cout << endl;

            if (ys.back() > puncte[i][j].second)
            {
                ys.push_back(puncte[i][j].second);
                total++;
            }
            else
            {
                //vector<long long>::iterator it = lower_bound(ys.rbegin(),ys.rend(),puncte[i][j].second);
                long long ll=0;
                long long rr = ys.size()-1;
                long long lastpos=0;
                while (ll<=rr)
                {
                    long long mid = (ll+rr)/2;
                    if (ys[mid]>puncte[i][j].second)
                    {
                        ll = mid+1;
                    }
                    else
                    {
                        rr = mid-1;
                        lastpos = mid;
                    }
                }
                ys[lastpos] = puncte[i][j].second;
            }
        }
    }
    fout << total;
}

/*
6 2  */