Cod sursa(job #3356441)

Utilizator Lex._.Lex Guiman Lex._. Data 1 iunie 2026 10:29:20
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#define NMAX 100000
#define x first
#define y second
using namespace std;

ifstream in("cadrane.in");
ofstream out("cadrane.out");

pair<int, int> puncte[NMAX+1];
int coord_x[NMAX+1], coord_y[NMAX+1];
vector<int> y_puncte[NMAX+1];

int aint[NMAX*4+1], lazy[NMAX*4+1];

void push(int nod, int st, int dr)
{
    if(st!=dr)
    {
        lazy[nod*2]+=lazy[nod];
        lazy[nod*2+1]+=lazy[nod];
    }
    aint[nod]+=lazy[nod];
    lazy[nod]=0;
}

void update(int l, int r, int val, int nod, int st, int dr)
{
    push(nod, st, dr);
    if(r<st || dr<l) return;
    if(l<=st && dr<=r) 
    {
        lazy[nod]+=val;
        push(nod, st, dr);
        return;
    }
    int mij=st+(dr-st)/2;
    update(l, r, val, nod*2, st, mij);
    update(l, r, val, nod*2+1, mij+1, dr);
    aint[nod]=min(aint[nod*2], aint[nod*2+1]);
}

int query(int l, int r, int nod, int st, int dr)
{
    push(nod, st, dr);
    if(l<=st && dr<=r) return aint[nod];
    if(r<st || dr<l) return NMAX;
    int mij=st+(dr-st)/2;
    return min(query(l, r, nod*2, st, mij), query(l, r, nod*2+1, mij+1, dr));
}

void afis(int nod, int st, int dr)
{
    push(nod, st, dr);
    if(st==dr) {out << aint[nod] << " "; return;}
    int mij=st+(dr-st)/2;
    afis(nod*2, st, mij);
    afis(nod*2+1, mij+1, dr);
}

int main()
{
    int n;
    in >> n;
    for(int i=1; i<=n; i++)
    {
        in >> puncte[i].x >> puncte[i].y;
        coord_x[i]=puncte[i].x;
        coord_y[i]=puncte[i].y;
    }
    sort(coord_x+1, coord_x+n+1);
    int cnt_x=unique(coord_x+1, coord_x+n+1)-coord_x-1;
    sort(coord_y+1, coord_y+n+1);
    int cnt_y=unique(coord_y+1, coord_y+n+1)-coord_y-1;
    //for(int i=1; i<=cnt_x; i++) out << coord_x[i] << " "; out << "\n";
    //for(int i=1; i<=cnt_y; i++) out << coord_y[i] << " "; out << "\n\n";
    for(int i=1; i<=n; i++)
    {
        puncte[i].x=lower_bound(coord_x+1, coord_x+cnt_x+1, puncte[i].x)-coord_x;
        puncte[i].y=lower_bound(coord_y+1, coord_y+cnt_y+1, puncte[i].y)-coord_y;

        //cout << puncte[i].x << " " << puncte[i].y << "\n";
        y_puncte[puncte[i].x].push_back(puncte[i].y);

        update(1, puncte[i].y, 1, 1, 1, cnt_y);
    }
    int p_max=0;
    for(int x=1; x<=cnt_x; x++)
    {
        //out << x << ": ";
        for(auto& y : y_puncte[x])
        {
            //out << y << " ";
            update(y+1, cnt_y, 1, 1, 1, cnt_y);
        } //out << "\n";
        //afis(1, 1, cnt_y); out << "\n";
        for(auto& y : y_puncte[x-1])
        {
            update(1, y-1, -1, 1, 1, cnt_y);
        }
        //afis(1, 1, cnt_y); out << "\n";
        //out << query(1, cnt_y, 1, 1, cnt_y) << "\n\n";
        p_max=max(p_max, query(1, cnt_y, 1, 1, cnt_y));
    }
    out << p_max;

    return 0;
}