Cod sursa(job #2738418)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 5 aprilie 2021 20:05:28
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <bits/stdc++.h>
using namespace std;
#define SERVER 0
const string nameFile="cadrane";
ifstream in (nameFile+".in");
ofstream out(nameFile+".out");
typedef pair<int, int> Pii;
#if (SERVER)
    #define in cin
    #define out cout
#endif
const int nmax=1e5;
int n;
Pii a[nmax+2];
vector <int> nrmX, nrmY;
inline Pii pSum(Pii p1, Pii p2){
    return make_pair(p1.first+p2.first, p1.second+p2.second);
}
struct segNode{
    Pii dp[2]; ///daca am aplicat deja operatia sau nu
    segNode(){
        dp[0]=dp[1]={0, 0};
    };
    friend segNode operator + (const segNode ss1, const segNode ss2){
        segNode temp;
        temp.dp[0]=pSum(ss1.dp[0], ss2.dp[0]);
        temp.dp[1]=min(pSum(ss1.dp[0], ss2.dp[1]), pSum(ss1.dp[1], make_pair(ss2.dp[0].second, ss2.dp[0].first)));
        return temp;
    }
};
class segTree{
public:
    vector <segNode> seg;
    int segSize;
    void assign(int n){
        segSize=n;
        seg.resize(2*n);
    }
    void pointUpdate(int poz, Pii val){
        updateUtil(0, 0, segSize-1, poz, val);
    }
    int totalQuery(){
        return seg[0].dp[1].first;
    }
private:
    void updateUtil(int pozAct, int st, int dr, int pozQ, Pii & valQ){
        if(st==dr){
            seg[pozAct].dp[0]=pSum(valQ, seg[pozAct].dp[0]);
            seg[pozAct].dp[1]=make_pair(seg[pozAct].dp[0].first+seg[pozAct].dp[0].second, seg[pozAct].dp[0].first+seg[pozAct].dp[0].second);
            return;
        }
        int mij=(st+dr)/2;
        if(pozQ<=mij)
            updateUtil(pozAct+1, st, mij, pozQ, valQ);
        else
            updateUtil(pozAct+2*(mij-st+1), mij+1, dr, pozQ, valQ);
        seg[pozAct]=seg[pozAct+1]+seg[pozAct+2*(mij-st+1)];
    }
};
segTree arb;
int main()
{
    in>>n;
    for(int i=1; i<=n; i++){
        in>>a[i].first>>a[i].second;
        nrmX.push_back(a[i].first), nrmY.push_back(a[i].second);
    }
    sort(nrmX.begin(), nrmX.end()), sort(nrmY.begin(), nrmY.end());
    nrmX.erase(unique(nrmX.begin(), nrmX.end()), nrmX.end()), nrmY.erase(unique(nrmY.begin(), nrmY.end()), nrmY.end());
    for(int i=1; i<=n; i++)
        a[i].first=lower_bound(nrmX.begin(), nrmX.end(), a[i].first)-nrmX.begin(),
        a[i].second=lower_bound(nrmY.begin(), nrmY.end(), a[i].second)-nrmY.begin();
    arb.assign(nrmY.size());
    for(int i=1; i<=n; i++)
        arb.pointUpdate(a[i].second, {0, 1});
    sort(a+1, a+n+1);
    int poz=1;
    int maxi=0;
    while(poz<=n){
        int pp=poz;
        while(pp<=n&&a[pp].first==a[poz].first){
            arb.pointUpdate(a[pp].second, {1, 0});
            pp++;
        }
        maxi=max(maxi, arb.totalQuery());
        for(int i=poz; i<pp; i++)
            arb.pointUpdate(a[i].second, {0, -1});
        poz=pp;
    }
    out<<maxi<<"\n";
    return 0;
}