Cod sursa(job #2725064)

Utilizator FrostfireMagirescu Tudor Frostfire Data 18 martie 2021 13:16:20
Problema Cadrane Scor 70
Compilator cpp-64 Status done
Runda simularesimulare Marime 1.58 kb
#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;
}