Cod sursa(job #2728318)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 23 martie 2021 00:40:51
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;

struct segment_tree{
    int mini,lazy;
} aint[DIM*4];

pair <int,int> v[DIM];
int X[DIM],Y[DIM];
vector <int> w[DIM];
int n,i,x,y;

int cautare_binara (int v[], int n, int val){
    int st = 1, dr = n;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (v[mid] == val)
            return mid;
        if (v[mid] < val)
            st = mid+1;
        else dr = mid-1;
    }
}

void update_lazy (int nod, int st, int dr){
    if (!aint[nod].lazy)
        return;
    if (st != dr){
        int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
        aint[fiu_st].mini += aint[nod].lazy;
        aint[fiu_st].lazy += aint[nod].lazy;

        aint[fiu_dr].mini += aint[nod].lazy;
        aint[fiu_dr].lazy += aint[nod].lazy;
    }
    aint[nod].lazy = 0;
}

void update (int nod, int st, int dr, int x, int y, int val){
    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){
        aint[nod].mini += val;
        aint[nod].lazy += val;
        update_lazy (nod,st,dr);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        update (nod<<1,st,mid,x,y,val);
    if (y > mid)
        update ((nod<<1)|1,mid+1,dr,x,y,val);

    update_lazy (nod<<1,st,mid);
    update_lazy ((nod<<1)|1,mid+1,dr);

    if (aint[nod<<1].mini < aint[(nod<<1)|1].mini)
        aint[nod].mini = aint[nod<<1].mini;
    else aint[nod].mini = aint[(nod<<1)|1].mini;
}

int main (){

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

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>v[i].first>>v[i].second;
        X[i] = v[i].first;
        Y[i] = v[i].second;
    }

    sort (X+1,X+n+1);
    int el = 1;
    for (i=2;i<=n;i++){
        if (X[i] != X[i-1])
            X[++el] = X[i];
    }

    sort (Y+1,Y+n+1);
    int el2 = 1;
    for (i=2;i<=n;i++){
        if (Y[i] != Y[i-1])
            Y[++el2] = Y[i];
    }

    for (i=1;i<=n;i++){
        int val = v[i].first;
        v[i].first = cautare_binara(X,el,val);
        val = v[i].second;
        v[i].second = cautare_binara(Y,el2,val);

        w[v[i].first].push_back(v[i].second);
    }

    for (i=1;i<=n;i++)
        update (1,1,el2,1,v[i].second,1);

    int pos = 1, sol = 0;
    for (i=1;i<=el;i++){
        /// adaug noua dreapta in aint
        for (auto it : w[i])
            update (1,1,el2,it,el2,1);

        /// trb sa sterg dreapta anterioara
        for (auto it : w[i-1])
            update (1,1,el2,1,it,-1);

        sol = max (sol,aint[1].mini);
    }

    cout<<sol<<"\n";

    return 0;
}