Cod sursa(job #3347952)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 18 martie 2026 23:43:14
Problema Cadrane Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <fstream>

#include <utility>
#define x first
#define y second

#include <algorithm>

using namespace std;

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

/** (<=, <=) & (>=, >=) countt **/
/** qwerty - vertical line (aka. x boundd) **/
typedef pair <int, int> pii;
const int nmax = 1e5, maxint = (1 << 30);
int n, maxpoints, unqyy; pii a[nmax + 2];

int getminpoints(int xx){
    int minpoints = maxint;

    for(int i = 1, score; i <= n; i++){

        pii py = make_pair(xx, a[i].y); score = 0;

        for(int j = 1; j <= n; j++){
            score += ((a[j].x <= py.x && a[j].y <= py.y) ||
                      (a[j].x >= py.x && a[j].y >= py.y));
        }

        minpoints = min(minpoints, score);
    }

    return minpoints;
}

pii norm[nmax + 2];
void normalizeyy(){
    for(int i = 1; i <= n; i++){
        norm[i] = make_pair(a[i].y, i);
    }

    sort(norm + 1, norm + 1 + n);

    for(int i = 1; i <= n; i++){
        unqyy += (norm[i].x != norm[i - 1].x || i == 1);
        a[norm[i].y].y = unqyy;
    }

    return;
}

struct segmenttree{
    int lazy[4 * nmax + 2];
    int treemin[4 * nmax + 2];

    void propagate(int node, int st, int dr){
        if(lazy[node] && st != dr){
            lazy[(node << 1)] += lazy[node];
            lazy[(node << 1) | 1] += lazy[node];

            treemin[(node << 1)] += lazy[node];
            treemin[(node << 1) | 1] += lazy[node];

            lazy[node] = 0;
        }
        return;
    }

    void update(int node, int st, int dr, int lff, int rgg, int valuee){
        propagate(node, st, dr);
        if(lff <= st && dr <= rgg){
            lazy[node] += valuee;
            treemin[node] += valuee;
        }else{
            int mij = (st + dr) >> 1;
            if(lff <= mij) update((node << 1), st, mij, lff, rgg, valuee);
            if(mij < rgg) update((node << 1) | 1, mij + 1, dr, lff, rgg, valuee);
            treemin[node] = min(treemin[(node << 1)], treemin[(node << 1) | 1]);
        }
    }

    int minquery(){ return treemin[1]; }
} myaint;

int main(){

    in>>n;
    for(int i = 1; i <= n; i++){
        in>>a[i].x>>a[i].y;
    }

    sort(a + 1, a + 1 + n);

    normalizeyy();

    for(int i = 1; i <= n; i++){ ///we do smth of a initializing
        myaint.update(1, 1, unqyy, a[i].y, unqyy, +1);
    }

    for(int i = 1, j = 1; i <= n; ){
        ///maxpoints = max(maxpoints, getminpoints(a[i].x));

        /// swap state of this point ///
        for(; j <= n && a[i].x == a[j].x; j++){
            myaint.update(1, 1, unqyy, a[j].y, unqyy, -1);
            myaint.update(1, 1, unqyy, 1, a[j].y, +1);
        }

        maxpoints = max(maxpoints, myaint.minquery());

        i = j;
    }

    out<<maxpoints<<"\n";

    return 0;
}