Cod sursa(job #2096369)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 29 decembrie 2017 00:10:31
Problema Cadrane Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <bits/stdc++.h>
#define MAXN 100000

#define BUF_SIZE 1 << 14
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline int nextnum(){
    int a = 0;
    char c = nextch();
    while(!isdigit(c))
        c = nextch();
    while(isdigit(c)){
        a = a * 10 + c - '0';
        c = nextch();
    }
    return a;
}

struct Biggus{
    int x, y;
} v[1 + MAXN];
bool cmp1(Biggus Dickus, Biggus Falus){
    return Dickus.x < Falus.x;
};
bool cmp2(Biggus Dickus, Biggus Falus){
    return Dickus.y < Falus.y;
};

int left, right, val;
int aint[4 * MAXN];
int lazy[4 * MAXN];
void update(int p, int st, int dr){
    if(left <= st && dr <= right){
        lazy[p] += val;
        aint[p] += lazy[p];
        if(st != dr){
            lazy[2 * p] += lazy[p];
            lazy[2 * p + 1] += lazy[p];
        }
        lazy[p] = 0;
    }
    else{
        lazy[2 * p] += lazy[p];
        lazy[2 * p + 1] += lazy[p];
        lazy[p] = 0;

        int m = (st + dr) / 2;
        if(left <= m) update(2 * p, st, m);
        if(m + 1 <= right) update(2 * p + 1, m + 1, dr);

        aint[p] = std::min(aint[2 * p] + lazy[2 * p], aint[2 * p + 1] + lazy[2 * p + 1]);
    }
}

int main(){
    fi = fopen("cadrane.in","r");
    fo = fopen("cadrane.out","w");

    int n = nextnum();
    for(int i = 1; i <= n; i++){
        v[i].x = nextnum();
        v[i].y = nextnum();
    }
    std::sort(v + 1, v + n + 1, cmp2);
    int prev = -1;
    for(int i = 1; i <= n; i++){
        if(prev == v[i].y){
            prev = v[i].y;
            v[i].y = v[i - 1].y;
        }
        else{
            prev = v[i].y;
            v[i].y = v[i - 1].y + 1;
        }
    }
    int last = v[n].y;
    std::sort(v + 1, v + n + 1, cmp1);
    for(int i = 1; i <= n; i++){
        left = 1;
        right = v[i].y;
        val = 1;
        update(1, 1, last);
    }

    int ind1 = 1, ind2;
    int max = -1;
    while(ind1 <= n){
        ind2 = ind1;
        while(ind2 <= n && v[ind2].x == v[ind1].x){
            left = v[ind2].y;
            right = last;
            val = 1;
            update(1, 1, last);
            ind2++;
        }
        max = std::max(max, aint[1]);
        ind2 = ind1;
        while(ind2 <= n && v[ind2].x == v[ind1].x){
            left = 1;
            right = v[ind2].y;
            val = -1;
            update(1, 1, last);
            ind2++;
        }
        ind1 = ind2;
    }
    fprintf(fo,"%d\n", max);

    fclose(fi);
    fclose(fo);
    return 0;
}