Cod sursa(job #1558210)

Utilizator cojocarugabiReality cojocarugabi Data 28 decembrie 2015 20:40:30
Problema Cadrane Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
# include <bits/stdc++.h>
# define x first
# define y second
using namespace std;
ifstream fi("cadrane.in");
ofstream fo("cadrane.out");
int sorted[1 << 18];
int a[1 << 17],b[1 << 17];
pair < int , int > s[1 << 20];
int val[1 << 18];
pair < int , int > min(pair < int , int > a,pair < int , int > b)
{
    if (a.x < b.x) return a;
    if (b.x < a.x) return b;
    return (a.y < b.y ? a : b);
}
void lazy(int p,int u,int node)
{
    if (p == u) return;
    int k = s[node].x - min(s[node << 1].x,s[node << 1 | 1].x);
    s[node << 1].x += k;s[node << 1 | 1].x += k;
}
void update(int p,int u,int l,int r,int val,int node)
{
    if (l > r) return;
    lazy(p,u,node);
    if (l <= p && u <= r) s[node].x += val;
    else
    {
        int m = (p + u) / 2;
        if (l <= m) update(p,m,l,r,val,node << 1);
        if (m+1<=r) update(m+1,u,l,r,val,node << 1 | 1);
        lazy(p,m,node << 1);
        lazy(m+1,u,node << 1 | 1);
        s[node] = min(s[node << 1],s[node << 1 | 1]);
    }
}
void build(int p,int u,int node)
{
    if (p == u) s[node] = {(val[p+1] == val[p] ? (int)(2e9):val[p]),p};
    else
    {
        int m = (p + u) / 2;
        build(p,m,node << 1);
        build(m+1,u,node << 1 | 1);
        s[node] = min(s[node << 1],s[node << 1 | 1]);
    }
}
int W = 0;
int bin(int val)
{
    int ans = 0;
    for (int i = 1 << 18;i;i >>= 1)
        if (ans + i <= W && sorted[ans + i] <= val) ans += i;
    return ans;
}
vector < int > q[1 << 18];
int main(void)
{
    set < int > w;
    int n;
    ios_base :: sync_with_stdio(0);
    fi>>n;
    for (int i = 1;i <= n;++i) fi>>a[i]>>b[i],w.insert(a[i]),w.insert(b[i]);
    for (auto it : w) sorted[++W] = it;
    for (int i = 1;i <= n;++i) a[i] = bin(a[i]),b[i] = bin(b[i]),++val[b[i]],q[a[i]].push_back(b[i]);
    for (int i = W-1;i;--i) val[i] += val[i+1];
    build(1,W,1);
    int ans = 0,dx,dy;
    for (int i = 1;i <= W;++i)
    if (!q[i].empty())
    {
        if (s[1].x > ans) ans = s[1].x,dx = i,dy = s[1].y;
        for (auto it : q[i])
        {
            update(1,W,1,it,-1,1);
            update(1,W,it,W,1,1);
        }
    }
    ans = 0;
    for (int i = 1;i <= n;++i) assert(dx != a[i] || dy != b[i]);
    for (int i = 1;i <= n;++i) ans += (a[i] > dx && b[i] > dy) || (a[i] < dx && b[i] < dy);
    for (int i = 1;i <= n;++i) ans += a[i] == dx,ans += b[i] == dy;
    return fo << ans << '\n',0;
}