Cod sursa(job #3257209)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 16 noiembrie 2024 21:45:25
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
int n, cnt = 0, sol[50010], rez = 0;
vector<int> cadran1, cadran2, cadran3, cadran4;

struct pereche {
    ///cine stie cunoaste
    int x, y;
    void read() { fin >> x >> y; }
}v[50010];
pereche start;

inline int cmp(int a, int b) { return v[a].x < v[b].x; }

int main()
{
    fin >> n;
    start.read();
    for(int i=1; i<=n; i++) {
        v[i].read();
        if(v[i].x <= start.x && v[i].y >= start.y) cadran1.push_back(i);
        else if(v[i].x >= start.x && v[i].y >= start.y) cadran2.push_back(i);
        else if(v[i].x >= start.x && v[i].y <= start.y) cadran3.push_back(i);
        else cadran4.push_back(i);
    }
    sort(cadran1.begin(), cadran1.end(), cmp);
    sort(cadran2.begin(), cadran2.end(), cmp);
    sort(cadran3.begin(), cadran3.end(), cmp);
    sort(cadran4.begin(), cadran4.end(), cmp);
    for(int i : cadran1) {
        int st = 1, dr = cnt, ans = -1;
        while(st <= dr) {
            int mid = (st + dr) / 2;
            if(sol[mid] <= v[i].y) ans = max(ans, mid), dr = mid - 1;
            else st = mid + 1;
        }
        if(ans == -1) sol[++cnt] = v[i].y;
        else sol[ans] = v[i].y;
    }
    rez += cnt, cnt = 0;
    for(int i : cadran2) {
        int st = 1, dr = cnt, ans = -1;
        while(st <= dr) {
            int mid = (st + dr) / 2;
            if(sol[mid] <= v[i].y) ans = max(ans, mid), dr = mid - 1;
            else st = mid + 1;
        }
        if(ans == -1) sol[++cnt] = v[i].y;
        else sol[ans] = v[i].y;
    }
    rez += cnt, cnt = 0;
    for(int i : cadran3) {
        int st = 1, dr = cnt, ans = -1;
        while(st <= dr) {
            int mid = (st + dr) / 2;
            if(sol[mid] <= v[i].y) ans = max(ans, mid), dr = mid - 1;
            else st = mid + 1;
        }
        if(ans == -1) sol[++cnt] = v[i].y;
        else sol[ans] = v[i].y;
    }
    rez += cnt, cnt = 0;
    for(int i : cadran4) {
        int st = 1, dr = cnt, ans = -1;
        while(st <= dr) {
            int mid = (st + dr) / 2;
            if(sol[mid] <= v[i].y) ans = max(ans, mid), dr = mid - 1;
            else st = mid + 1;
        }
        if(ans == -1) sol[++cnt] = v[i].y;
        else sol[ans] = v[i].y;
    }
    rez += cnt, cnt = 0;
    fout << rez;

    return 0;
}