Cod sursa(job #1487598)

Utilizator akaprosAna Kapros akapros Data 17 septembrie 2015 08:54:24
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define maxN 50002
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define nrC 4
using namespace std;
int x, y, w[maxN], n, i, j, sol;
pair < int , int > vi;
int cmp (pair <int, int> a, pair <int, int> b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.y;
}
vector < pair <int, int> > V[nrC];
void read()
{
    freopen("pachete.in", "r", stdin);
    scanf("%d", &n);
    scanf("%d %d", &x, &y);
    for (i = 1; i <= n; ++ i)
    {
        scanf("%d %d", &vi.x, &vi.y);
        vi.x -= x;
        vi.y -= y;
        if (vi.x > 0 && vi.y > 0)
            V[0].pb(mp(vi.x, vi.y));
        else if (vi.x > 0 && vi.y < 0)
            V[1].pb(mp(vi.x, -vi.y));
        else if (vi.x < 0 && vi.y > 0)
            V[2].pb(mp(-vi.x, vi.y));
        else
            V[3].pb(mp(-vi.x, -vi.y));
    }
}
int bs(int x)
{
    int i = 0, p = 1 << 15;
    while (p)
    {
        if (i + p <= w[0] && w[i + p] <= x)
            i += p;
        p /= 2;
    }
    return i;
}
void solc(int a)
{
    int i, p;
    for (i = 0; i < V[a].size(); ++ i)
    {
        if (i == 0 || V[a][i].y >= w[w[0]])
           w[++ w[0]] = V[a][i].y;
        else
        {
            p = bs(V[a][i].y);
            w[p] = V[a][i].y;
        }
    }
}
void solve()
{
    for (i = 0; i < nrC; ++ i)
    {
        sort(V[i].begin(), V[i].end(), cmp);
        solc(i);
        sol += w[0];
        w[0] = 0;
    }
}
void write()
{
    freopen("pachete.out", "w", stdout);
    printf("%d", sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}