Cod sursa(job #3364212)

Utilizator Turcanu_DavidTurcanu David Turcanu_David Data 31 august 2026 14:55:24
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;

struct SegTree
{
    struct Node
    {
        int min1;
        int prop;

        Node operator+(Node b)
        {
            return {min(min1, b.min1), 0};
        }
    };

    Node T[MAXN * 4];

    int n;

    void init(int N)
    {
        n = N;
    }

    void push(int i, bool lf)
    {
        T[i].min1 += T[i].prop;
        if(!lf)
        {
            T[i * 2].prop += T[i].prop;
            T[i * 2 + 1].prop += T[i].prop;
        }
        T[i].prop = 0;
    }

    void update0(int i, int l, int r, int ql, int qr, int dt)
    {
        push(i, (l == r));
        if(r < ql || qr < l)
            return;
        if(ql <= l && r <= qr)
        {
            T[i].prop = dt;
            push(i, (l == r));
            return;
        }
        int mid = (l + r) / 2;
        update0(i * 2, l, mid, ql, qr, dt);
        update0(i * 2 + 1, mid + 1, r, ql, qr, dt);
        T[i] = (T[i * 2] + T[i * 2 + 1]);
    }

    void update(int l, int r, int dt)
    {
        update0(1, 0, n - 1, l, r, dt);
    }

    int query()
    {
        push(1, (0 == n - 1));
        return T[1].min1;
    }
};

SegTree aint;

int n;

int x[MAXN], y[MAXN];

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ifstream cin("cadrane.in");
    ofstream cout("cadrane.out");
    cin >> n;
    vector<int> xs, ys;
    for(int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
        xs.push_back(x[i]);
        ys.push_back(y[i]);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    vector<vector<int>> pts;
    pts.resize(xs.size());

    aint.init(ys.size());
    for(int i = 0; i < n; i++)
    {
        x[i] = lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin();
        y[i] = lower_bound(ys.begin(), ys.end(), y[i]) - ys.begin();
//        cerr << x[i] << ' ' << y[i] << '\n';
        aint.update(0, y[i], 1);
        pts[x[i]].push_back(y[i]);
    }
    int ans = 0;
    for(int i = 0; i < pts.size(); i++)
    {
        sort(pts[i].begin(), pts[i].end());
        for(int y : pts[i])
        {
            aint.update(y + 1, ys.size() - 1, 1);
        }
        ans = max(ans, aint.query());
        for(int y : pts[i])
        {
            aint.update(0, y - 1, -1);
        }
    }
    cout << ans;
    return 0;
}