Cod sursa(job #3364205)

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

using namespace std;
const int MAXN=1e5+5;
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];
int ny=0;

void norm(int n){
    map<int, int> mp;
    for(int i=0; i<n; i++)
        mp[p[i].y]=1;
    for(auto e : mp)
        mp[e.first]=++ny;
    for(int i=0; i<n; i++)
        p[i].y=mp[p[i].y];
}

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, ny);
    for(int i=0; i<n; i++)
        aint.update(1, 1, ny, 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++)
            aint.update(1, 1, ny, p[k].y, ny, 1);
        ans=max(ans, aint.query());
        for(int k=i; k<j; k++)
            aint.update(1, 1, ny, 1, p[k].y, -1);
        i=j;
    }
    cout<<ans<<"\n";
    return 0;
}