Cod sursa(job #3364202)

Utilizator stefanvil3Stefan Vilcescu stefanvil3 Data 31 august 2026 14:19:08
Problema Cadrane Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <bits/stdc++.h>

using namespace std;
const int MAXN=1e5;
const int MOD=1e9+7;
using ll=long long;

struct LazySegmentTree{
    int aint[4*MAXN+1];
    int lazy[4*MAXN+1];
    void init(int node, int st, int dr){
        aint[node]=0;
        lazy[node]=0;
        if(st==dr)
            return;
        int mij=(st+dr)/2;
        init(2*node, st, mij);
        init(2*node+1, mij+1, dr);
    }
    void push(int node, int x){
        aint[node]+=x;
    }
    void propag(int node){
        if(lazy[node]!=0){
            lazy[2*node]+=lazy[node];
            push(2*node, lazy[node]);
            lazy[2*node+1]+=lazy[node];
            push(2*node+1, lazy[node]);
            lazy[node]=0;
        }
    }
    void update(int node, int st, int dr, int l, int r, int x){
        if(st>=l && dr<=r){
            push(node, x);
            lazy[node]+=x;
            return;
        }
        propag(node);
        int mij=(st+dr)/2;
        if(mij>=l)
            update(2*node, st, mij, l, r, x);
        if(mij<r)
            update(2*node+1, mij+1, dr, l, r, x);
        aint[node]=min(aint[2*node], aint[2*node+1]);
    }
    int query(){
        return aint[1];
    }
};

LazySegmentTree aint;

struct point{
    int x, y;
    bool operator <(const point &a){
        if(x!=a.x)
            return x<a.x;
        return y<a.y;
    }
};

point p[MAXN];
int s[MAXN];

void norm(int n){
    for(int i=0; i<n; i++)
        s[i]=p[i].y;
    sort(s, s+n);
    for(int i=0; i<n; i++){
        int st=-1, dr=n-1;
        while(dr-st>1){
            int mij=(st+dr)/2;
            if(s[mij]<p[i].y)
                st=mij;
            else
                dr=mij;
        }
        p[i].y=dr+1;
    }
}

int main(){
//    ifstream cin("cadrane.in");
//    ofstream cout("cadrane.out");
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>p[i].x>>p[i].y;
    sort(p, p+n);
    norm(n);
    aint.init(1, 1, n);
    for(int i=0; i<n; i++)
        aint.update(1, 1, n, 1, p[i].y, 1);
    int i=0;
    int ans=aint.query();
    while(i<n){
        int j=i;
        while(j<n && p[i].x==p[j].x)
            j++;
        for(int k=i; k<j; k++){
            cout<<k<<" "<<p[k].y<<"\n";
            aint.update(1, 1, n, p[k].y, n, 1);
        }
        ans=max(ans, aint.query());
        for(int k=i; k<j; k++)
            aint.update(1, 1, n, 1, p[k].y, -1);
        i=j;
    }
    cout<<ans<<"\n";
    return 0;
}