Cod sursa(job #2147970)

Utilizator retrogradLucian Bicsi retrograd Data 1 martie 2018 13:47:40
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <bits/stdc++.h>

using namespace std;

struct SegmentTree {
    int n;
    vector<int> T, L;
    SegmentTree(int n) : n(n), T(4 * n), L(4 * n) {}

    void update(int node, int b, int e, int l, int r, int val) {
        if (l > r) return;
        if (b == l && e == r) {
            L[node] += val;
            T[node] += val;
            return;
        }
        int m = (b + e) / 2;
        update(node * 2, b, m, l, min(r, m), val);
        update(node * 2 + 1, m + 1, e, max(l, m + 1), r, val);
        T[node] = min(T[node * 2], T[node * 2 + 1]) + L[node];
    }
    void Add(int l, int r, int val) {
        return update(1, 0, n - 1, l, r, val);
    }
    int Query() { return T[1]; }
};

int main() {
    ifstream cin("cadrane.in");
    ofstream cout("cadrane.out");

    int n; cin >> n;
    vector<int> all_x, all_y;
    vector<pair<int, int>> P;
    for (int i = 0; i < n; ++i) {
        int x, y; cin >> x >> y;
        all_x.push_back(x);
        all_y.push_back(y);
        P.emplace_back(x, y);
    }

    auto Unique = [&](vector<int>& v) {
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
    };
    auto Norm = [&](int x, vector<int>&xs) {
        auto it = lower_bound(xs.begin(), xs.end(), x);
        assert(it != xs.end() && *it == x);
        return distance(xs.begin(), it);
    };
    Unique(all_x);
    Unique(all_y);

    sort(P.begin(), P.end());
    SegmentTree st(all_y.size());
    

    auto Add = [&](pair<int, int> where, int what, bool dw) {
        int pos = Norm(where.second, all_y);
        if (dw) st.Add(0, pos, what);
        else    st.Add(pos, all_y.size() - 1, what);
    };

    for (int i = 0; i < n; ++i)
        Add(P[i], +1, true);
    
    int at = 0, ret = -250000;
    for (auto x : all_x) {
        int nxt = at; 
        while (nxt < n && P[nxt].first == x)
            ++nxt;

        for (int i = at; i < nxt; ++i)
            Add(P[i], +1, false);
        
        ret = max(ret, st.Query());

        for (int i = at; i < nxt; ++i)
            Add(P[i], -1, true);
        at = nxt;
    }
    cout << ret << endl;
    return 0;
}