Cod sursa(job #2478037)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 21 octombrie 2019 16:10:07
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;

int sgn(int num) {
        if (num >= 0)
                return +1;
        else
                return -1;
}

int get(int x, int y) {
        int a = sgn(x), b = sgn(y);
        if (a == -1)
                if (b == -1)
                        return 0;
                else
                        return 1;
        else
                if (b == -1)
                        return 2;
                else
                        return 3;
}

int main()
{
        freopen ("pachete.in", "r", stdin);
        freopen ("pachete.out", "w", stdout);

        int n;
        cin >> n;
        vector <vector <pair <int, int>>> rofl(4);

        for (int i = 0; i < n; i++) {
                int x, y;
                cin >> x >> y;
                rofl[get(x, y)].push_back({abs(x), abs(y)});
        }

        int ans = 0;
        for (auto &vec : rofl) {
                sort(vec.begin(), vec.end());
                vector <int> turkish;
                for (auto &it : vec) {
                        int x = it.second;
                        if (turkish.empty() || x < turkish.back()) {
                                turkish.push_back(x);
                                continue;
                        }
                        int l = 0, r = (int) turkish.size() - 1, pos;
                        while (l <= r) {
                                int mid = (l + r) / 2;
                                if (x >= turkish[mid]) {
                                        pos = mid;
                                        r = mid - 1;
                                } else {
                                        l = mid + 1;
                                }
                        }
                        turkish[pos] = x;
                }
                ans += (int) turkish.size();
        }
        cout << ans << "\n";

        return 0;
}