Pagini recente » Cod sursa (job #2718255) | Cod sursa (job #3204304) | Cod sursa (job #888761) | Cod sursa (job #431571) | Cod sursa (job #2725064)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define f first
#define s second
#define NMAX 100000
using namespace std;
ifstream fin("cadrane.in");
ofstream fout("cadrane.out");
int n, ans, curr;
pair <int, int> v[NMAX+10], aint[NMAX+10];
vector <pair <int, int> > a;
void update(int nod, int stnod, int drnod, int stu, int dru, int val)
{ if(stu <= stnod && drnod <= dru)
{ aint[nod].f += val;
aint[nod].s += val;
return;
}
aint[2*nod].f += aint[nod].s;
aint[2*nod].s += aint[nod].s;
aint[2*nod+1].f += aint[nod].s;
aint[2*nod+1].s += aint[nod].s;
aint[nod].s = 0;
int mij = (stnod + drnod) / 2;
if(stu <= mij)
update(2*nod, stnod, mij, stu, dru, val);
if(dru > mij)
update(2*nod+1, mij+1, drnod, stu, dru, val);
aint[nod].f = min(aint[2*nod].f, aint[2*nod+1].f);
}
int main()
{
fin >> n;
for(int i=1; i<=n; i++)
{ int x, y;
fin >> x >> y;
v[i].f = x;
a.push_back({y, i});
}
sort(a.begin(), a.end());
curr = 1;
v[a[0].s].s = 1;
for(int i=1; i<a.size(); i++)
{ if(a[i].f != a[i-1].f)
curr++;
v[a[i].s].s = curr;
}
sort(v+1, v+n+1);
int bit = 0;
while((1 << bit) < curr)
bit++;
curr = (1 << bit);
for(int i=1; i<=n; i++)
update(1, 1, curr, 1, v[i].s, 1);
int p = 1;
for(int i=2; i<=n+1; i++)
if(v[i].f != v[i-1].f)
{ for(int j=p; j<i; j++)
update(1, 1, curr, 1, v[j].s, -1);
ans = max(ans, aint[1].f + i - p);
for(int j=p; j<i; j++)
update(1, 1, curr, v[j].s, curr, 1);
p = i;
}
fout << ans << '\n';
return 0;
}