Cod sursa(job #3304510)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 24 iulie 2025 13:20:24
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
#define int long long
int n;

struct Iris {
    int x, y;

    void read() { fin >> x >> y; }
    Iris() { x = y = 0; }
    Iris(int a, int b) { x = a, y = b; }
    bool operator == (const Iris &p) const { return p.x == x && p.y == y; }
    bool operator < (const Iris &p) const { return x < p.x || (x == p.x && y < p.y); }
    bool operator > (const Iris &p) const { return x > p.x || (x == p.x && y > p.y); }
}start;
vector<Iris> v1, v2, v3, v4;
vector<int> maxim;

inline int cmp(Iris a, Iris b) {
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

signed main()
{
    fin >> n;
    start.read();
    for(int i=1; i<=n; i++) {
        Iris p; p.read();
        if(p.x >= start.x && p.y >= start.y) v1.push_back(p);
        else if(p.x >= start.x && p.y <= start.y) v2.push_back(p);
        else if(p.x <= start.x && p.y <= start.y) v3.push_back(p);
        else v4.push_back(p);
    }
    int rez = 0;
    sort(v1.begin(), v1.end(), cmp);
    for(Iris i : v1) {
        int st = 0, dr = maxim.size() - 1;
        while(st <= dr) {
            int mid = (st + dr) / 2;
            if(maxim[mid] > i.y) st = mid + 1;
            else dr = mid - 1;
        }
        if(st < maxim.size()) maxim[st] = i.y;
        else maxim.push_back(i.y);
    }
    rez += maxim.size(), maxim.clear();
    sort(v2.begin(), v2.end(), cmp);
    for(Iris i : v2) {
        int st = 0, dr = maxim.size() - 1;
        while(st <= dr) {
            int mid = (st + dr) / 2;
            if(maxim[mid] > i.y) st = mid + 1;
            else dr = mid - 1;
        }
        if(st < maxim.size()) maxim[st] = i.y;
        else maxim.push_back(i.y);
    }
    rez += maxim.size(), maxim.clear();
    sort(v3.begin(), v3.end(), cmp);
    for(Iris i : v3) {
        int st = 0, dr = maxim.size() - 1;
        while(st <= dr) {
            int mid = (st + dr) / 2;
            if(maxim[mid] > i.y) st = mid + 1;
            else dr = mid - 1;
        }
        if(st < maxim.size()) maxim[st] = i.y;
        else maxim.push_back(i.y);
    }
    rez += maxim.size(), maxim.clear();
    sort(v4.begin(), v4.end(), cmp);
    for(Iris i : v4) {
        int st = 0, dr = maxim.size() - 1;
        while(st <= dr) {
            int mid = (st + dr) / 2;
            if(maxim[mid] > i.y) st = mid + 1;
            else dr = mid - 1;
        }
        if(st < maxim.size()) maxim[st] = i.y;
        else maxim.push_back(i.y);
    }
    rez += maxim.size(), maxim.clear();
    fout << rez;

    return 0;
}