Cod sursa(job #3364271)

Utilizator Iustin_Mircea2010Iustin Mircea Iustin_Mircea2010 Data 31 august 2026 21:58:24
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <bits/stdc++.h>

using namespace std;

struct point{
    int x, y;
}v[100005];

int aint[400005], lazy[400005];

void push(int i, int l, int r){
    if(lazy[i] == 0) return;
    aint[i] += lazy[i];
    if(l != r){
        lazy[2 * i] += lazy[i];
        lazy[2 * i + 1] += lazy[i];
    }
    lazy[i] = 0;
}

void update(int i, int l, int r, int ql, int qr, int val){
    push(i, l, r);
    if(l > qr || ql > r) return;
    if(ql <= l && r <= qr){
        lazy[i] += val;
        push(i, l, r);
        return;
    }
    int mid = l + r >> 1;
    update(2 * i, l, mid, ql, qr, val);
    update(2 * i + 1, mid + 1, r, ql, qr, val);
    aint[i] = min(aint[2 * i], aint[2 * i + 1]);
}

int aux[100005], nm[100005];
vector<int> coord[100005];

int main(){

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

    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> v[i].x >> v[i].y;
        aux[i] = v[i].x;
    }
    sort(aux + 1, aux + n + 1);
    for(int i = 1; i <= n; i++){
        if(aux[i] == aux[i - 1] && i > 1) nm[i] = nm[i - 1];
        else
            nm[i] = nm[i - 1] + 1;
    }
    for(int i = 1; i <= n; i++){
        v[i].x = lower_bound(aux + 1, aux + n + 1, v[i].x) - aux;
        v[i].x = nm[v[i].x];
    }
    int nx = nm[n];
    for(int i = 1; i <= n; i++){
        aux[i] = v[i].y;
    }
    sort(aux + 1, aux + n + 1);
    for(int i = 1; i <= n; i++){
        if(aux[i] == aux[i - 1] && i > 1) nm[i] = nm[i - 1];
        else
            nm[i] = nm[i - 1] + 1;
    }
    int ny = nm[n];
    for(int i = 1; i <= n; i++){
        v[i].y = lower_bound(aux + 1, aux + n + 1, v[i].y) - aux;
        v[i].y = nm[v[i].y];
        update(1, 1, ny, 1, v[i].y, 1);
        coord[v[i].x].push_back(v[i].y);
    }
    int ans = 0;
    for(int i = 1; i <= nx; i++){
        for(int y : coord[i]){
            update(1, 1, ny, 1, y, -1);
        }
        push(1, 1, ny);
        ans = max(ans, aint[1] + (int)coord[i].size());
        for(int y : coord[i]){
            update(1, 1, ny, y, ny, 1);
        }
    }
    cout << ans << '\n';

    return 0;
}