Cod sursa(job #1558193)

Utilizator cojocarugabiReality cojocarugabi Data 28 decembrie 2015 20:11:07
Problema Cadrane Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
# include <bits/stdc++.h>
using namespace std;
ifstream fi("cadrane.in");
ofstream fo("cadrane.out");
int sorted[1 << 18];
int a[1 << 17],b[1 << 17];
int s[1 << 20];
int val[1 << 18];
void lazy(int p,int u,int node)
{
    if (p == u) return;
    int k = s[node] - min(s[node << 1],s[node << 1 | 1]);
    s[node << 1] += k;s[node << 1 | 1] += 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] += 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]);
    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;
    for (int i = 1;i <= W;++i)
    if (!q[i].empty())
    {
        ans = max(ans,s[1] == 2e9 ? 0 : s[1]);
        for (auto it : q[i])
        {
            update(1,W,1,it,-1,1);
            update(1,W,it,W,1,1);

        }
    }
    return fo << ans << '\n',0;
}