Cod sursa(job #2100744)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 6 ianuarie 2018 11:54:33
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.71 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = (int) 1e5;

pair <int, int> pts[MAXN + 1];

vector < pair <int, int> > vx, vy;

inline void norm(vector < pair <int, int> > &v, bool t) {
    sort(v.begin(), v.end());
    int sz = v.size();
    int val = 1;
    if(t == 0)
        pts[v[0].second].first = 1;
    else
        pts[v[0].second].second = 1;
    for(int i = 1; i < sz; i++) {
        if(v[i].first != v[i - 1].first)
            val++;
        if(t == 0)
            pts[v[i].second].first = val;
        else
            pts[v[i].second].second = val;
    }
}

pair <int, int> aint[4 * MAXN + 1];

inline void prop(int nod) {
    if(2 * nod + 1 <= 4 * MAXN) {
        aint[2 * nod].second += aint[nod].second;
        aint[2 * nod + 1].second += aint[nod].second;
    }
}

inline void solve_lazy(int nod) {
    prop(nod);
    aint[nod].first += aint[nod].second;
    aint[nod].second = 0;
}

void build(int nod, int left, int right, int pos, int val) {
    if(left == right) {
        aint[nod].first = val;
    }
    else {
        int med = (left + right) / 2;
        if(pos <= med)
            build(2 * nod, left, med, pos, val);
        else
            build(2 * nod + 1, med + 1, right, pos, val);
        aint[nod].first = min(aint[2 * nod].first, aint[2 * nod + 1].first);
    }
}

void update(int nod, int left, int right, int l, int r, int val) {
    if(l > r)
        return ;
    solve_lazy(nod);
    if(l <= left && right <= r) {
        aint[nod].second += val;
        solve_lazy(nod);
    }
    else {
        int med = (left + right) / 2;
        if(l <= med)
            update(2 * nod, left, med, l, r, val);
        if(med < r)
            update(2 * nod + 1, med + 1, right, l, r, val);
        solve_lazy(2 * nod);
        solve_lazy(2 * nod + 1);
        aint[nod].first = min(aint[2 * nod].first, aint[2 * nod + 1].first);
    }
}

/*void query(int nod, int left, int right) {
    solve_lazy(nod);
    if(left == right) {
        printf("%d " ,aint[nod].first);
    }
    else {
        int med = (left + right) / 2;
        query(2 * nod, left, med);
        query(2 * nod + 1, med + 1, right);
    }
}*/

int main() {
    FILE *fi, *fout;
    int i, j, n, x, y;
    fi = fopen("cadrane.in" ,"r");
    fout = fopen("cadrane.out" ,"w");
    fscanf(fi,"%d " ,&n);
    for(i = 1; i <= n; i++) {
        fscanf(fi,"%d %d " ,&x,&y);
        vx.push_back({x, i});
        vy.push_back({y, i});
    }
    norm(vx, 0);
    norm(vy, 1);
    int my = pts[vy.back().second].second;
    for(i = 1; i <= 4 * my; i++) {
        aint[i].first = 2 * MAXN;
    }
    int cnt = 0;
    i = n - 1;
    while(i >= 0) {
        y = pts[vy[i].second].second;
        j = i;
        while(j >= 0 && vy[i].first == vy[j].first) {
            if(pts[vy[j].second].first > 1)
               cnt++;
            j--;
        }
        build(1, 1, my, y, cnt);
        i = j;
    }
    cnt = 0;
    for(i = 1; i <= n; i++) {
        if(pts[i].first == 1) {
            cnt++;
        }
    }
    int ans = 0;
    i = cnt;
    while(i < n) {
        ans = max(ans, aint[1].first + cnt);
        j = i - 1;
        while(j >= 0 && vx[i - 1].first == vx[j].first) {
            y = pts[vx[j].second].second;
            update(1, 1, my, y, my, 1);
            j--;
        }
        j = i;
        cnt = 0;
        while(j < n && vx[i].first == vx[j].first) {
            y = pts[vx[j].second].second;
            cnt++;
            update(1, 1, my, 1, y, -1);
            j++;
        }
        i = j;
    }
    ans = max(ans, aint[1].first + cnt);
    fprintf(fout,"%d" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}